Cryptography-Digest Digest #725
Cryptography-Digest Digest #725, Volume #13 Tue, 20 Feb 01 20:13:00 EST
Contents:
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
("Doom the Mostly Harmless")
Re: Is there an algorithm to sequentially enumerate all transcendental numbers?
(Paul Rubin)
Re: Rnadom Numbers ("Joseph Ashwood")
Re: Big Numbers in C/C++ ("Joseph Ashwood")
Re: Super strong crypto ("Joseph Ashwood")
Re: A seriously different cipher concept (long) ("Paul Pires")
Re: New unbreakable code from Rabin? (Kenneth Almquist)
Re: 448 bits Hash algorithm ("Joseph Ashwood")
Re: New unbreakable code from Rabin? (John Savard)
Re: Random number encryption (John Savard)
Re: Is there an algorithm to sequentially enumerate all transcendental (Robert
Glass)
Re: New unbreakable code from Rabin? (Charles Blair)
Re: New unbreakable code from Rabin? (mike vernal)
Re: New unbreakable code from Rabin? (Sundial Services)
From: "Doom the Mostly Harmless" [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: Tue, 20 Feb 2001 22:22:37 GMT
"Dik T. Winter" [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
In article 8Oek6.8603$[EMAIL PROTECTED] "Doom the
Mostly Harmless" [EMAIL PROTECTED] writes:
It is impossible to create an ordinal set of trancendental numbers
because
between any two given, there is an infinite number.
I do not know what you mean by "ordinal set". But when you mean
"enumeration"
you are correct, but for the wrong reason. For instance, the rational
numbers
I apologize if I was unclear. I'm someone who is good at math, not a
mathematician, so it's entirely likely I got it wrong.
I was trying to answer what I thought the originator of this discussion
meant, rather than what he actually asked. What I was attempting to say is
that there's no way to say "this is the first, and this is the second, etc."
in numerical order. I suppose that if you were to pick one method for
generating them and a fixed starting point, you could come up with a
consistent ordering based on that, but that didn't seem to be what he was
asking for.
I admit, a bit of this discussion has sailed over my head, but I suspect
that it has for the originator, as well. If it's not, I apologize for
slighting him. :-)
Anyway, I was simply trying to be clear, rather than rigorous.
--
To air is human
--Doom.
--
From: Paul Rubin [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: Is there an algorithm to sequentially enumerate all transcendental
numbers?
Date: 20 Feb 2001 14:26:59 -0800
Doug Kuhlman [EMAIL PROTECTED] writes:
Are there any non-diagonalization proofs?
Yes. At the very least, you can prove it with a power set argument
(prove no set can have the same cardinality as its power set ...)
That is a diagonalization proof ;-)
--
From: "Joseph Ashwood" [EMAIL PROTECTED]
Subject: Re: Rnadom Numbers
Date: Wed, 14 Feb 2001 11:51:11 -0800
"Douglas A. Gwyn" [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
Mok-Kong Shen wrote:
and that black box does not have other entropy input,
A "black box" practically by definition has some entropy
associated with it
I suppose you could make an argument for that stand on the basis of unknown
design. I would personally count that as a one time addition of entropy, so
if you use the box once and only once you get the full amount of added
entropy, but in general you only get 1/(number of times it's been used
entropy) added from it, so at infinite (where most computer science
discussions take place), there is no entropy added by the device. So in
reality there is some addition of entropy, but I feel it can and should be
ignored.
Joe
--
From: "Joseph Ashwood" [EMAIL PROTECTED]
Subject: Re: Big Numbers in C/C++
Date: Wed, 14 Feb 2001 12:03:13 -0800
"Edward Rustin" [EMAIL PROTECTED] wrote in message Does anyone know
where I can find information about working with big (1024
bit+) numbers under C or C++?
openSSL has one, www.openssl.org
Joe
--
From: "Joseph Ashwood" [EMAIL PROTECTED]
Subject: Re: Super strong crypto
Date: Wed, 14 Feb 2001 12:39:16 -0800
I think I have insite into real security, of course everyone should know by
now that I am not averse to an extended conversation about it.
Actually I should rephrase that, I think I have an understanding of the
requirements to secure data as much as possible, that exceeds the general
statements made on this group (including those often made
Cryptography-Digest Digest #725
Cryptography-Digest Digest #725, Volume #12 Wed, 20 Sep 00 13:13:00 EDT Contents: Re: Hamming weight (Mack) Re: Maximal security for a resources-limited microcontroller (Runu Knips) Re: Hardware RNGs (Mark Carroll) Re: Algebra, or are all block ciphers in trouble? (Mack) Re: Software patents are evil. (Tim Tyler) Re: SUN SPOT 6.51 BILLION square kilometers in size (Eugene Griessel) Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption (David Empey) Re: My attempt at an alogrithm. (Runu Knips) Re: RSA Questions ([EMAIL PROTECTED]) From: [EMAIL PROTECTED] (Mack) Subject: Re: Hamming weight Date: 20 Sep 2000 16:18:42 GMT Mack, I'm a bit puzzled: A good definition for base two. But Hamming weight is also applicable to other bases. "The Theory of Error-Correcting Codes" by MacWilliams and Sloane defines the Hamming Weight as the number of non-zero entries in the numeric string and the Hamming Distance as the number of places where they differ or alternately the hamming weight of subtracting one string from the other without carry. Francois Grieu answered that the Hamming weight was only depending on the binary representation. The Hamming weight of 19 is thus 3 (2^4, 2^1 and 2^0). If it's applicable to other bases shouldn't 19 have a weight of 2 (1*10^1 and 9*10^0) ?? Kim That is still calculating the base two weight. In base ten the weight is 2. In base 3 the number is (2*3^2+1*3^0) which is also hamming weight 2. Since 19 is prime it will have hamming weight of 2 for all bases up to 18 except base 2. In fact any prime will always have a hamming weight of at least 2 for bases smaller than itself. Mack Remove njunk123 from name to reply by e-mail -- Date: Wed, 20 Sep 2000 18:18:56 +0200 From: Runu Knips [EMAIL PROTECTED] Subject: Re: Maximal security for a resources-limited microcontroller Sagie wrote: I'm in need of a symmetric (secret key) encryption process for one of my projects. I would love to use one of the popular schemes, such as blowfish and DES, but the cipher has to be implemented in a teeny-weeny microcontroller with very limited resources. The cipher's program footprint, memory footprint and execution time must therefore be as small as possible, while maintaining the highest security possible (I was thinking about a process that will take no more than 150 RISC cycles per byte, and a program footprint of no more than 384 words). Plus I'm also quite a novice in these issues. We have discussed this issue here before a while. Skipjack was the cipher which was finally suggested. It is very slow (compared to the AES ciphers, on a normal PC or Workstation) and has only a 80 bit key (Schneider suggested once in his A.C. one shouldn't use key sizes below 112 bit), but it might be implemented in really low resource environments. What I had in mind was to implement a non-linear 4-bit or 8-bit lookup table (8-bit lookup table is as far as I can go -- and it must be used for both encryption and decryption, which is not a big deal because I can decide that incoming messages will be encrypted with the decryption key), along with maybe some bit splicing. The last line of defence I was thinking of is somehow making the encryption of every byte dependant of the encryption result of the last byte. But this raises question as for implementing the decryption process... So this is basically what I'm asking: 1. Is the "progressive ciphering" (the "last line of defence" described in the last paragraph) at all possible to perform? If so, how is the encryption/decryption implemented? (I would appreciate a tutorial source code/link) 2. Can anyone direct me to a source code that demonstrates (and explains) how do table-based ciphers are implemented? 3. Is there anything else that can be performed to raise the security level (within the limits described above)? 4. After doing all of these tricks, how strong is the cipher going to be? I hope I'm not asking too much here... I would appreciate any help, really. Well maybe you would like to get a skipjack source: /* ** Skipjack algorithm, from sci.crypt. ** Edited for better readability - Runu Knips */ /* Subject: Re: Skipjack implementation in C (this one works) Date: Thu, 18 May 2000 23:09:24 GMT From: "Douglas A. Gwyn" [EMAIL PROTECTED] Organization: @Home Network Newsgroups: sci.crypt SKIPJACK implementation in Standard C last edit: 25-Jan-1999 [EMAIL PROTECTED] This is a C89 implementation of the SKIPJACK block cipher algorithm described in version 2.0 of NSA's SKIPJACK specification dated 29 May 1998 http://csrc.nist.gov/encryption/skipjack-kea.htm. */ #ifdef DEBUG #includestdio.h #endif /* ** Interface specification: */ #define SJ_Keysize
Cryptography-Digest Digest #725
Cryptography-Digest Digest #725, Volume #11 Sun, 7 May 00 16:13:01 EDT
Contents:
How does PGP passphrase produce the session key ? ("Thierry FALISSARD")
Re: zeroknowledge.com and freedom.net - Snake oil? (Roger)
Factoring RSA ([EMAIL PROTECTED])
Re: Fresco transmits my name (was: Spammed after just visiting a site) (Mark Wooding)
Re: How does PGP passphrase produce the session key ? (Tom St Denis)
Newbie question about primes ("JoeC")
Re: Newbie question about primes (Earl K. Nimoy)
Re: Joystick as RNG (Sandy Harris)
Re: Tempest Attacks with EMF Radiation (Diet NSA)
Re: SBOX using boolean logic (Terry Ritter)
Re: Fresco transmits my name (was: Spammed after just visiting a site) (James
MacDonald)
Re: Fresco transmits my name (was: Spammed after just visiting a site) (James
MacDonald)
Re: Fresco transmits my name (was: Spammed after just visiting a site) (Terry Blunt)
Re: Newbie question about primes (Sandy Harris)
From: "Thierry FALISSARD" [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp,comp.security.pgp.tech
Subject: How does PGP passphrase produce the session key ?
Date: Sun, 7 May 2000 19:48:23 +0200
I know the passphrase is hashed to produce the session key
(I am interested here only in conventional encryption).
If the passphrase is hashed by MD5, the size of the hash will be 128 bits.
If the encryption algorithm is 3DES, 168 bits of key are required.
How does PGP create the missing key bits ?
--
From: Roger [EMAIL PROTECTED]
Subject: Re: zeroknowledge.com and freedom.net - Snake oil?
Date: Sun, 07 May 2000 10:50:05 -0700
"David A. Wagner" wrote:
In article [EMAIL PROTECTED], Steve [EMAIL PROTECTED] wrote:
And BTW, since the Freedom Network does not use latency or remix
to muddy the digital trail, traffic analysis can determine who
any user is, provided that someone with sufficient interest and
funding cares.
Care to elaborate? That was not my impression at all.
After all, I thought the whole architecture was based on mixing,
so I'm not sure where your comments are coming from, but I'd be
happy to be educated on what they're doing wrong.
They can't do everything. If you are the only one using a
particular server and someone monitors that server, then
presumably traffic analysis will yield some info. Maybe
not very much, but I think it is enough to keep Freedom Net
from making absolute claims of anonymity.
--
From: [EMAIL PROTECTED]
Subject: Factoring RSA
Date: Sun, 07 May 2000 17:54:33 GMT
I would like to know, given a factoring time ot Ft for an n digit RSA,
how to claculate the asymptotic time increment Ft' for n' (n'n) for
the following algorithms:
CFRAC
GNFS
SNFS
Thanks
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: [EMAIL PROTECTED] (Mark Wooding)
Crossposted-To: comp.sys.acorn.misc
Subject: Re: Fresco transmits my name (was: Spammed after just visiting a site)
Date: 7 May 2000 17:52:32 GMT
Rev. James Cort [EMAIL PROTECTED] wrote:
In article [EMAIL PROTECTED], Mark Wooding
[EMAIL PROTECTED] writes
* The symmetric session keys are too short. A space of 2^{128} bits
can be searched in less than a week given the sort of computing
power available to the US government.
IMHO, Most likely possibility. Intel admit to having some *much* faster
processors operating in their labs than anything generally available.
Why shouldn't the government have similar or greater levels of computing
power which *aren't* known about?
2^{128} is a big number. Let's assume, sort of for the sake of
argument, that Intel have designed terahertz processors, and for some
reason aren't selling them to anyone outside the US government. Let's
assume that they can do one key schedule *and* encryption *every* cycle.
To keep the numbers nice, let's say that that's 2^{40} encryptions every
*second*.
Now let's say that they have a million of these things. That's another
2^{20} factor. We're up to 2^{60} keys tested every second. (At this
point, we can find 16 DES keys per second.)
Hmm. We're still a factor of 2^{68} off where we want to be. Breaking
a 128-bit cipher, by brute force, with the computational resources
described above (not corrected for Moore's law) will take 2^{68}
seconds. That's unfortunate, because 2^{68} seconds is a little over 9
billion years.
Which is more than a week, I believe.
Let's correct for Moore's law. Let t be the time, in seconds, where 0
is now. Let Y be the number of seconds in a year: Y = 31,557,600.
I'll take Moore's law as `speed doubles every 18 months'. If the number
of keys-per-second at time t is E(t), then the number of keys-per-second
at time t + 3Y/2 is E(t + 3Y/2) = 2 E(t). A little bit of maths shows
that E(t) = E(0) k^t works well as a model, where k = 2^{
Cryptography-Digest Digest #725
Cryptography-Digest Digest #725, Volume #10 Sun, 12 Dec 99 03:13:02 EST
Contents:
Re: Brute Force Time (Maximum v Probable) (Scott Nelson)
Re: Synchronised random number generation for one-time pads ("Charles Meigh")
Re: Brute Force Time (Maximum v Probable) (Bill Unruh)
Re: New RNG Technique (Guy Macon)
Re: New RNG Technique (Guy Macon)
Re: Insecure PRNG? ("Gary")
Re: Random Noise Encryption Buffs (Look Here) (Guy Macon)
Re: Random Noise Encryption Buffs (Look Here) (Guy Macon)
Re: Synchronised random number generation for one-time pads (Guy Macon)
Re: low exponent in Diffie-hellman? (jerome)
Re: New Algorithm (Tim Tyler)
Re: Linear Congruential Generators ("Steven Alexander")
Re: New RNG Technique ("Steven Alexander")
Re: New Algorithm ("Steven Alexander")
Re: some questions about DES (jerome)
Re: If you're in Australia, the government has the ability to modify your files.
4.Dec.1999 (zapzing)
Encryption of I-Mail? Someone Invent this Please! (UBCHI2)
Re: Encryption of I-Mail? Someone Invent this Please! (Nike Y. Molar)
Re: Encryption of I-Mail? Someone Invent this Please! (UBCHI2)
Re: Encryption of I-Mail? Someone Invent this Please! (Johnny Bravo)
Re: Attacks on a PKI (lcs Mixmaster Remailer)
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Brute Force Time (Maximum v Probable)
Reply-To: [EMAIL PROTECTED]
Date: Sat, 11 Dec 1999 21:24:22 GMT
On 11 Dec 1999 19:35:59 GMT, [EMAIL PROTECTED] (UBCHI2) wrote:
1) You have a 50% chance of finding the key after only running only half the
possible keys. Basically, there is a 1 in 2 chance of the attack taking only
half the time allocated given the total possible number of keys.
2) You only have to search for keys equal to the keylength of the target. For
example, you only have to search for a key equal to 128, 256, 512, 1024. I
estimate that less than 1 in 100 people use a key of an "off" size. You don't
have to search for all keys smaller than 128. This cuts the number of keys
down by perhaps 50%.
In other words, .5*.5 is only 25%. This corresponds to the time needed to
attack a key with brute force versus the time allocated given the total number
of possible keys.
The industry should shift from quoting maximum time to crack a key to quoting
probable time to crack a key.
Producers who list the time taken to break a cipher in a
particular way, have an interest in having it be as large
as possible. In other words, they want you to view their
products in the best possible light. Consumers on the other
hand, have an interest in having uniform numbers to make
comparison "shopping" easier.
Given these two goals, it's seems better to choose
the most generous numbers possible - if you don't
then an unscrupulous producer can dupe some consumers
with inferior products. Not that they won't anyway,
but there's no reason to make it easy for them.
Scott Nelson [EMAIL PROTECTED]
--
From: "Charles Meigh" [EMAIL PROTECTED]
Subject: Re: Synchronised random number generation for one-time pads
Date: Fri, 10 Dec 1999 20:57:04 -
Guy Macon wrote in message ...
(Charles Meigh) wrote:
I'm still thinking that there might be some
vastly wide choice of 'celestial' events that could produce truly random
numbers that will still be sufficiently similar observed from any two (or
more) points on the globe, which would make OTP use more economical.
You have that already. Just generate your random numbers using whatever
method you prefer and post them in a newsgroup. Or you can put them on
a CD and sell the CD on a web site. Or broadcast them with a ham radio.
Getting your random numbers to two or more points on the globe is trivial.
What is hard is getting your random numbers to exactly two (and no more
than two) points on the globe and not to any other points on the globe.
Alas, the latter is what you need if you want to have the shared secret
that is the basis of OTP encryption.
But would those methods realistically allow you to distribute a sufficiently
large set of random data that from which enough potential OTP keys can be
generated without allowing brute force attacks. Interception of the pool
of random data is not a concern if it is large enough.
--
Charles Meigh
--
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Brute Force Time (Maximum v Probable)
Date: 11 Dec 1999 22:13:08 GMT
In [EMAIL PROTECTED] [EMAIL PROTECTED] (UBCHI2)
writes:
...
The industry should shift from quoting maximum time to crack a key to quoting
probable time to crack a key.
The estimates are so crude that the difference between the two is
irrelevant.
--
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: New RNG Technique
Date: 11 Dec 1999 17:13:52
Cryptography-Digest Digest #725
Cryptography-Digest Digest #725, Volume #9 Tue, 15 Jun 99 20:13:02 EDT
Contents:
Re: Cracking DES (David Wagner)
SLIDE ATTACK large state SYSTEMS (SCOTT19U.ZIP_GUY)
Re: SLIDE ATTACK large state SYSTEMS (David Wagner)
Re: Export restrictions question ([EMAIL PROTECTED])
Re: TEA vs Blowfish ([EMAIL PROTECTED])
Signing with two keys and verifying use one the key? (Yang Yang)
Test, please ignore (Yang Yang)
Re: Algorithm from easy spec please! ([EMAIL PROTECTED])
Challenge: signing with two keys, verifiable with one of the key, but can not fake
with one key? (Yang Yang)
Re: SLIDE ATTACK large state SYSTEMS (SCOTT19U.ZIP_GUY)
Re: [Q]: Session key exchange ([EMAIL PROTECTED])
Re: DES and BPANN (James Pate Williams, Jr.)
Re: DES (Jerry Coffin)
Re: "Breaking" a cipher ("Steven Alexander")
Re: DES (Jim Gillogly)
Secret info for MACS (Casey Sybrandy)
Re: DES lifetime (was: being burnt by the NSA) (Jerry Coffin)
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Cracking DES
Date: 15 Jun 1999 12:04:15 -0700
In article 7k5tfs$pui$[EMAIL PROTECTED], [EMAIL PROTECTED] wrote:
Let us suppose that 2^73 bytes of memory is actually feasible. I
understand that for this attack to work we would need about 2^140
memory accesses.
Not quite right; the naive MITM attack takes 2^73 bytes of memory
and 2^70 memory accesses. A considerable improvement over exhaustive
search, but still, as you say, not very practical due to the massive
memory requirements.
An improvement that drastically reduces the memory requirements
(at some modest cost in computational complexity) is van Oorschot
and Wiener's parallel collision search techniques. See e.g. their
paper on breaking double-DES; I think it was in a recent CRYPTO.
In general, I would argue that it would be prudent to assume that
a cleverer adversary might be able to find an algorithm that entirely
eliminates the memory requirements, leaving a MITM attack that takes
just 2^70 operations. I think it is entirely possible that such an
algorithm exists, given van Oorschot and Wiener's clever techniques.
I think that the cryptanalytic community should agree on an attack cost
function that is more appropriate than just counting encryptions. In an
official comment to NIST I have proposed a simple metric towards that
end.
Ooh! I agree: I think this is a very interesting research question.
I wonder whether you can approximate the cost pretty well as a linear
function of the resource requirements, at least for some resources.
For instance,
1 MB of fast memory ~ 100 MB of slow memory
~ 2^36 trial encryptions / year ~ 1 KB of known plaintext
(These are just examples, I don't know if they're reasonable estimates.)
I'll look forward to reading your comment to NIST. Is it available?
--
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: SLIDE ATTACK large state SYSTEMS
Date: Tue, 15 Jun 1999 19:20:46 GMT
Lets look at the Slide Attack as it applies to a
large key system instead of a small key of a mere
few hundred bits or less. The problem with small
keyed systems is that after only a few dozen bytes
if the encrpyted message came from text there is generally
only one solution as to what that text is.
This weakness is also exploited by methods such as
the slide attack where one searchs for slide pairs
and then checks to see if the single round has a
has a solution. If it does then this solution is
the one that is assumed to be the one for the multi
round case. This is a good attack for small key
systems but lets look a theoritical large key system
where it fails. This is a theorictical system only
suppose I represent it by a large S box that is re
peated twice. Such the C0 = F ( F (P0) ) this is
just the S-box repeated twice in series. The method can
be such that instead of keeping the S box in memory
The entry is calculated on the fly as the data is
available. OF course it could have been respresent by
one S-box but is wasn't. The task is to find entries
in the S-box so that the function used can be found
lets assume that if all zeores goes in all zeros
come out. That is as simple a slide pair you can get
the all zero case. Know you look at the basic S box
and see of there is a entry where 0 gets mapped to
zero lets say there is a valid set of keys that produce
this as a solution actaully if your method almost allows
for all S-tables there are many such possible keys that
could lead to this. Kow you think you have part
of the soultion. But in realitiy 0 could map to 1 and
1in stage 1. In the second stage 1 could map to 0. So that both
the slide critea are meet in that over all 0 can map to
0 and in the single stage. But it was not in the one
used in the code. As the key space gets large these
false soultions get more common. This is just a simple
example to show how one can be mislead in trying
