Cryptography-Digest Digest #779, Volume #13 Fri, 2 Mar 01 12:13:01 EST
Contents:
Re: How good is the KeeLoq algorithm? (Frank Gerlach)
Re: RC4 like stream cipher ("Henrick Hellstr�m")
Re: Good Security Products?? (Frank Gerlach)
Re: super-stong crypto, straw man phase 2 (SCOTT19U.ZIP_GUY)
Re: RSA Key Generation ("Michael Scott")
Re: repeating codes ("r.e.s.")
Will RIJNDAEL EVER HAVE BIJECTIVE MODES? (SCOTT19U.ZIP_GUY)
Re: repeating codes (John Shonder)
Re: Will RIJNDAEL EVER HAVE BIJECTIVE MODES? ("Tom St Denis")
Re: super-stong crypto, straw man phase 2 ("Tom St Denis")
Re: RC4 like stream cipher ("Scott Fluhrer")
Re: RSA Key Generation ("Tom St Denis")
Re: RC4 like stream cipher ("Tom St Denis")
HMAC-SHA1 with new version of SHA1-256, 384, 512 ("Ludovic Flament")
Re: repeating codes (Gary Wong)
Re: Text of Applied Cryptography (Mike Marshall)
Re: RSA Key Generation ("Jakob Jonsson")
Re: philosophical question? (Mike Rosing)
----------------------------------------------------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: How good is the KeeLoq algorithm?
Date: Fri, 02 Mar 2001 16:12:15 +0100
> Actually 32 bit block, 64 bit key
Ok, I admit that this makes a brute-force attack for the mafia quite
infeasible.
But the following is still highly suspicious:
"KEELOQ is a proprietary block cipher based on a block length of 32 bits
and a key length of 64 bits. The algo-rithm is characterized by a very
economical hardware implementation, while retaining a level of security
com-parable to Data Encryption Standards (DES)."
This seems to indicate that it is a modification of DES. The slightest
modifications to an algorithm can easily make it very weak, which you
can see by looking at other threads in this group. Only review by
experienced codebreakers will make an algorithm safe (or kill it). Their
unwillingness to make the algorithm public seems to confirm that they
believe in "security by obscurity".
The GSM crypto algorithm also seems to be strong based on its keyspace,
but it can be broken in near-realtime with a PC, because it has some
(deliberate ?) weaknesses.
I would still propose to use a well-reviewed, but simple algorithm like
RC4.
Check http://www.counterpane.com/crypto-gram for more on that.
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 2 Mar 2001 16:18:31 +0100
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:mJBn6.349$[EMAIL PROTECTED]...
>
> "Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
> news:97mo69$2c3$[EMAIL PROTECTED]...
> > I found a crack with a 90% success rate and less than 7% false hits
given
> > 2048 bytes of known plain text. The major problem is step 4. Your
proposed
> > modification of step 3 did not have any impact whatsoever on the success
> > rate of this attack. I simply exploited the weakness intruduced by step
4
> > you outlined yourself and wrapped it in a brute force attack on the
2-byte
> > state.
>
> Hmm if you wrote your attack in C I could try this myself but...
I know of no development environment as productive as Delphi. If I had to
write it in C I would not write it at all, because I wouldn't have the time.
But C and Pascal aren't that different. Translating from Pascal to C is
rather straight-forward:
Change "begin" to "{", "end" to "}", ":=" to "=", "=" to "==", "." to "->",
"Inc(x,y)" to "x += y", "and" to either "&" or "&&", etc. Change "array"
types to pointer types and initialize them in code. Change "record" types to
"struct" types. Swap the order of variables and types in variable
declarations, swap the order of result types and function names in function
declarations, etc. Remove the word "const" from the parameter list of
functions - it only results in compiler errors if the parameter is assigned
to inside the function. Replace "var"-parameters by pointer type parameters.
Change "while" and "repeat" statements to "for" statements. Etc. In some C
dialects all of these changes will not be necessary.
The only major obstacles are calls to library routines (there is a call to
Move(Source,Dest,Count) in my code) and Pascal sets (none in the code I
presented here).
> Try changing to
>
> 1. t1 <= S[sy]
> 2. swap S[sy] with S[sx]
> 3. sy <= (sy + sx + 1) mod 256
> 4. sx <= t1
> 5. return t1
Same result as before. Remember, I brute force sx and sy, so I have already
eliminated the question marks in your equations.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Good Security Products??
Date: Fri, 02 Mar 2001 16:30:30 +0100
Matthias Bauer wrote:
>
> Hi Frank,
>
> Thank you, but am looking for more - I have to make a compairson table of
> serveral providers......
Maybe you have to do the homework on your own :-)
try +jca +jsse in altavista
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: super-stong crypto, straw man phase 2
Date: 2 Mar 2001 15:44:53 GMT
[EMAIL PROTECTED] (wtshaw) wrote in <jgfunj-0203010023290001@dial-245-
214.itexas.net>:
>In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
><[EMAIL PROTECTED]> wrote:
>
>> William Hugh Murray wrote:
>> > "Douglas A. Gwyn" wrote:
>> > > William Hugh Murray wrote:
>> > > > In any case, most of us do not worry about keeping secrets from
>> > > > nation states for a long time.
>> > > Well, you should!
>> > I admit that I do like to confound authority.
>>
>> Another point is that "super strong crypto" ought to mean that
>> *nobody* can come up with a practical attack; if you allow that
>> some "nation-state" can successfully attack a given system, then
>> that demonstrates that that system was not "super strong".
>
>Ciphers can be separated into groups according to my scale founded on
>Shannon's unicity concept. The groups are trivial, weak, marginally
>strong, strong, and very strong. Trivial is up to 128 bits, while strong
>is at least 92,593 bits of text.
I guess that means by your classifcation scott16u could easily
be far more secure than any of the proposed AES ciphers that most
users will be tricked into using. Since it is one of the few
ciphers that takes Shannons's unicity concept seriously.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: RSA Key Generation
Date: Fri, 2 Mar 2001 09:53:14 -0600
Its also good to keep p and q as far apart as possible.
One way is to fix the top nibble of p as F and the top nibble of q as 9.
This "F9" rule doesn't reveal anything of practical use for cryptanalysis
Mike Scott
"Mark Reed" <[EMAIL PROTECTED]> wrote in message
news:2cGn6.56062$[EMAIL PROTECTED]...
> Hi all !
>
> This is my first post (though you might say I'm a long time listener), so
> sorry if this has already been asked....
>
> In RSA key generation, 2 primes are found by getting random data and
setting
> the most and least significant bits are set to ensure the prime length is
> half the required modulus length and that it is odd. Then this is
checked,
> then the next candidate (say by adding two) until it is 'probably prime'
> enough for use.
>
> If only the top bit is set, the key length may be one less than required -
> as an example for a 512 bit RSA key with
> p = 0x80......
> q = 0x80......
>
> then
>
> n = 0x40......
>
> My question is whether this is common practice, or if generally the top
two
> bits of each prime
> (guaranteeing n > 0x90......)
>
> I suppose another possibility is that primes are generated until n is the
> required bitlength.
>
> Unless this method is used, isn't security compromised ? ie. n can be
less
> than the number of bits required or the top two bits of each prime are
known
> to be one.
>
> Thanks in advance,
>
> Mark.
>
>
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: repeating codes
Date: Fri, 2 Mar 2001 08:04:10 -0800
"Frank Gerlach" <[EMAIL PROTECTED]> wrote ...
| If you have 8 letters,
| it will be (26+10)^8==100000026 possible codes.
36^8 = 2,821,109,907,456
--r.e.s.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Will RIJNDAEL EVER HAVE BIJECTIVE MODES?
Date: 2 Mar 2001 16:06:34 GMT
I looked at various FIPS and RFC that may be implimented for
the new AES cipher. My fear is that not even one fully bijective
mode will be allowed.
I thought people would at least look at Matt Timmermans cool
implimentation of RIJNDAEL that is bijective. But it seems that
the phony crypto gods are either to stupid to understand what he
did or they don't want only those who kiss assed there way into the
closed group.
For others of you out there in crypto land. Would it be nice
to have a version of RIJNDAEL that handles all 8-bit binary files
so that any file could be uniquely encrypted? And would it not
be nice to have a encryption mode that can treat any file as
an encrypted file. What I mean by this last statement is
if one tests a worng key it can lead uniquely to file that when
encrypted comes back to the same file.
There are many methods that can do these transformations in a
fully bijective way. You don't even need special modes of
RIJNDAEL to make the concept work. You can even use it in ECB
mode with full blocks only.
The key is to convert any file to a "finitely odd file"
then convert that back to the unque file of the desired block
size. Then encrypt the file with standard RIJNDAEL.
At which point you convert it back to "finitely odd file"
and then convert that to 8-bit binary file.
This is not that hard I can put all the intermediate programs
on a page at my site. So user only needs the ECB full BLOCK
RIJNDAEL code for middle stage.
If one wants more security and likes the god of random
one can even have more than one RIJNDEAL encryption and
use my rotate file program with correct conversions so
that more than one pass of RIJNDEAL occurs over randomly
rotated files.
If an enemy tries to test a wrong set of keys it will
still be unique to a unique file and random values will be such
that if you reencrypt and use random values that pop out with
wrong key you get the same file back. It works for any 8-bit
binary type of file.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: John Shonder <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: repeating codes
Date: Fri, 02 Mar 2001 11:06:47 -0500
I may be wrong, but I think the birthday paradox comes into play here, and he will
generate "one of the previously generated codes" in many fewer trials.
Frank Gerlach wrote:
> If you have 8 letters, it will be (26+10)^8==100000026 possible codes.
> So if you have a simple counter, you will generate an identical number
> after about 100 Million numbers generated. If you use a pseudo-random
> number generator, chances can differ widely, depending on the generator.
> Also be aware of the fact that some(most ?) pseudo random number
> generators will allow you to easily calculate number R(n) from R(n-1).
> The rand() implementation of most C runtime systems is an example of
> this.
> >
> > Hi,
> >
> > I generate random codes like the following:
> > H5R6-8UPG
> > where each digit is 0-9, A-Z
> >
> > Now, if I start to generate these random codes today how many can I generate
> > before there is a probability that I will hit one of the previously
> > generated codes? And how do you work that out anyway?
> >
> > Any info would be great,
> >
> > Eric
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Will RIJNDAEL EVER HAVE BIJECTIVE MODES?
Date: Fri, 02 Mar 2001 16:15:39 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I looked at various FIPS and RFC that may be implimented for
> the new AES cipher. My fear is that not even one fully bijective
> mode will be allowed.
> I thought people would at least look at Matt Timmermans cool
> implimentation of RIJNDAEL that is bijective. But it seems that
> the phony crypto gods are either to stupid to understand what he
> did or they don't want only those who kiss assed there way into the
> closed group.
>
> For others of you out there in crypto land. Would it be nice
> to have a version of RIJNDAEL that handles all 8-bit binary files
> so that any file could be uniquely encrypted? And would it not
> be nice to have a encryption mode that can treat any file as
> an encrypted file. What I mean by this last statement is
> if one tests a worng key it can lead uniquely to file that when
> encrypted comes back to the same file.
Apparently you didn't read all the papers. The CTR mode can encrypt single
bit files just as easily as 8-bit or 128-bit ones.
Go back to lalala land.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 02 Mar 2001 16:16:15 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (wtshaw) wrote in <jgfunj-0203010023290001@dial-245-
> 214.itexas.net>:
>
> >In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> ><[EMAIL PROTECTED]> wrote:
> >
> >> William Hugh Murray wrote:
> >> > "Douglas A. Gwyn" wrote:
> >> > > William Hugh Murray wrote:
> >> > > > In any case, most of us do not worry about keeping secrets from
> >> > > > nation states for a long time.
> >> > > Well, you should!
> >> > I admit that I do like to confound authority.
> >>
> >> Another point is that "super strong crypto" ought to mean that
> >> *nobody* can come up with a practical attack; if you allow that
> >> some "nation-state" can successfully attack a given system, then
> >> that demonstrates that that system was not "super strong".
> >
> >Ciphers can be separated into groups according to my scale founded on
> >Shannon's unicity concept. The groups are trivial, weak, marginally
> >strong, strong, and very strong. Trivial is up to 128 bits, while strong
> >is at least 92,593 bits of text.
>
> I guess that means by your classifcation scott16u could easily
> be far more secure than any of the proposed AES ciphers that most
> users will be tricked into using. Since it is one of the few
> ciphers that takes Shannons's unicity concept seriously.
So you have cryptanalysis of scottu16u? Can I read it?
Tom
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 2 Mar 2001 08:08:42 -0800
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:DhNn6.4225$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:97nkv1$r7j$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:mJBn6.349$[EMAIL PROTECTED]...
> > >
> > > "Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
> > > news:97mo69$2c3$[EMAIL PROTECTED]...
> > > > I found a crack with a 90% success rate and less than 7% false hits
> > given
> > > > 2048 bytes of known plain text. The major problem is step 4. Your
> > proposed
> > > > modification of step 3 did not have any impact whatsoever on the
> success
> > > > rate of this attack. I simply exploited the weakness intruduced by
> step
> > 4
> > > > you outlined yourself and wrapped it in a brute force attack on the
> > 2-byte
> > > > state.
> > >
> > > Hmm if you wrote your attack in C I could try this myself but...
> > >
> > > Try changing to
> > >
> > > 1. t1 <= S[sy]
> > > 2. swap S[sy] with S[sx]
> > > 3. sy <= (sy + sx + 1) mod 256
> > > 4. sx <= t1
> > > 5. return t1
> >
> > That's just as bad. If the attacker sees the digraph (a, b) on the
> output,
> > he then knows that, after that digraph has been output, S[a]==b. And,
if
> > the attacker assumes sy at one point (that is, he cycles through all 256
> > possible sy values), he can track the value of sy at all times, since he
> > knows sx at all times and sx is the only thing that modifies sy. Ok,
it's
> > slightly better in that the attacker has to try 256 values of sy, rather
> > than be given it.
> >
> > So, for every output, a byte of the array is revealed. And, once the
> > attacker knows it, he can keep track of it forever. So, after a
thousand
> or
> > so outputs, the attacker knows the vast majority of the array state...
>
> Ah, but you're slightly wrong. You are given S[sy] and are never given
sy.
> So you know there is a byte "t1" in the array but you don't know where
Actually, you do. You might not were it was (unless you know sy, which
isn't that difficult), but you do where it is now (!). Here are the steps
you take (starting at step 4 of the first output of the digraph):
4. sx := t1
We'll call the current value of t1 'a'
5. return a
The attacker now knows the current value of sx.
1.t1 := S[sy]
We'll call the new value of t1 'b'
2. S[a] := b
This step actually sets S[sx] to S[sy], but since a == Sx and S[sy]==b,
the above description is accurate. This step also modifies S[sy], but we're
not interested in that array element for this analysis
3.
4.
Neither of these steps affects either t1 or the array element at S[a],
so for this analysis, they can be ignored.
5. return b
And so, at this point, S[a] == b.
> And
> you know in the next byte that the positions (?, sx) are used in the
swaps.
> You never know what "sy" is though directly.
Going through all 256 possible initial values is not that difficult. And,
since the attacker always knows the value of sx, given the initial value of
sy, he then knows the value of sy throughout the cipher.
--
poncho
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RSA Key Generation
Date: Fri, 02 Mar 2001 16:17:41 GMT
"Michael Scott" <[EMAIL PROTECTED]> wrote in message
news:isPn6.37330$[EMAIL PROTECTED]...
> Its also good to keep p and q as far apart as possible.
>
> One way is to fix the top nibble of p as F and the top nibble of q as 9.
> This "F9" rule doesn't reveal anything of practical use for cryptanalysis
That's a neat trick. However, it's extemely unlikely that the two numbers
are close enough to make Fermats method work, etc..
Two random 512-bit primes are likely to be at least 2^128 away.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 02 Mar 2001 16:19:38 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:97oh16$al6$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:DhNn6.4225$[EMAIL PROTECTED]...
> >
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > news:97nkv1$r7j$[EMAIL PROTECTED]...
> > >
> > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > news:mJBn6.349$[EMAIL PROTECTED]...
> > > >
> > > > "Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
> > > > news:97mo69$2c3$[EMAIL PROTECTED]...
> > > > > I found a crack with a 90% success rate and less than 7% false
hits
> > > given
> > > > > 2048 bytes of known plain text. The major problem is step 4. Your
> > > proposed
> > > > > modification of step 3 did not have any impact whatsoever on the
> > success
> > > > > rate of this attack. I simply exploited the weakness intruduced by
> > step
> > > 4
> > > > > you outlined yourself and wrapped it in a brute force attack on
the
> > > 2-byte
> > > > > state.
> > > >
> > > > Hmm if you wrote your attack in C I could try this myself but...
> > > >
> > > > Try changing to
> > > >
> > > > 1. t1 <= S[sy]
> > > > 2. swap S[sy] with S[sx]
> > > > 3. sy <= (sy + sx + 1) mod 256
> > > > 4. sx <= t1
> > > > 5. return t1
> > >
> > > That's just as bad. If the attacker sees the digraph (a, b) on the
> > output,
> > > he then knows that, after that digraph has been output, S[a]==b. And,
> if
> > > the attacker assumes sy at one point (that is, he cycles through all
256
> > > possible sy values), he can track the value of sy at all times, since
he
> > > knows sx at all times and sx is the only thing that modifies sy. Ok,
> it's
> > > slightly better in that the attacker has to try 256 values of sy,
rather
> > > than be given it.
> > >
> > > So, for every output, a byte of the array is revealed. And, once the
> > > attacker knows it, he can keep track of it forever. So, after a
> thousand
> > or
> > > so outputs, the attacker knows the vast majority of the array state...
> >
> > Ah, but you're slightly wrong. You are given S[sy] and are never given
> sy.
> > So you know there is a byte "t1" in the array but you don't know where
> Actually, you do. You might not were it was (unless you know sy, which
> isn't that difficult), but you do where it is now (!). Here are the steps
> you take (starting at step 4 of the first output of the digraph):
>
> 4. sx := t1
> We'll call the current value of t1 'a'
> 5. return a
> The attacker now knows the current value of sx.
> 1.t1 := S[sy]
> We'll call the new value of t1 'b'
> 2. S[a] := b
> This step actually sets S[sx] to S[sy], but since a == Sx and
S[sy]==b,
> the above description is accurate. This step also modifies S[sy], but
we're
> not interested in that array element for this analysis
> 3.
> 4.
> Neither of these steps affects either t1 or the array element at
S[a],
> so for this analysis, they can be ignored.
> 5. return b
>
> And so, at this point, S[a] == b.
Oh ok I see how it's used now. I knew that giving it out was a bad idea.
On the plus side it's an amazingly simple PRNG although it's insecure....
Thanks alot guys for the discussion :-)
Tom
------------------------------
From: "Ludovic Flament" <[EMAIL PROTECTED]>
Subject: HMAC-SHA1 with new version of SHA1-256, 384, 512
Date: Fri, 2 Mar 2001 17:22:03 +0100
Hi,
Is anyone have Tests Vector, or know where I can find it, for HMAC-SHA1
with SHA1-256, SHA1-384 and SHA1-512 ?
I just find Tests Vector for HMAC-SHA1 with SHA1-160.
Thanks,
--
Ludovic FLAMENT
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Gary Wong <[EMAIL PROTECTED]>
Subject: Re: repeating codes
Date: Fri, 2 Mar 2001 16:22:38 GMT
"Eric Mosley" <[EMAIL PROTECTED]> writes:
> I generate random codes like the following:
> H5R6-8UPG
> where each digit is 0-9, A-Z
>
> Now, if I start to generate these random codes today how many can I generate
> before there is a probability that I will hit one of the previously
> generated codes? And how do you work that out anyway?
There are 36^8 possible codes, so if you assume you already have n
unique codes and pick one code from the uniform distribution of all
36^8 of them, then the probability of a collision is exactly n/36^8,
or about n in 3 trillion.
However, if you take n independent samples from a uniform distribution
over k possibilities, then as a rule of thumb, you encounter
significant probability of a collision once n is of the order of
sqrt(k) -- this is the "Birthday Paradox"; try a web search on that
name for more information. This suggests that you want to stay well
below 36^4, or about 2 million, if you're trying to avoid a collision.
All of this assumes the random selection is i.i.d. (independent and
identically distributed). Any correlation between the samples could
drastically increase or decrease the probabilities.
Cheers,
Gary.
--
Gary Wong Consultant, Dependable Distributed Computing, AT&T Shannon Labs
[EMAIL PROTECTED] http://www.cs.arizona.edu/~gary/
------------------------------
From: [EMAIL PROTECTED] (Mike Marshall)
Crossposted-To: alt.anonymous.messages,alt.security.pgp,talk.politics.crypto
Subject: Re: Text of Applied Cryptography
Date: 2 Mar 2001 10:53:12 -0500
Heck, I just lined up to pay $50.00 for a copy down at
the news stand... Isn't Bruce still kind of counting on that?
-Mike
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: RSA Key Generation
Date: Fri, 2 Mar 2001 17:38:14 +0100
I don't think this helps. If xp is close to yq for any known numbers x, y
(not necessarily x=y=1), then you are in danger:
For any x,y we have
(xp+yq) - 2*sqrt(xyn)
(xp+yq)^2-4*xyn
= ----------------
xp+yq+2*sqrt(xyn)
(xp-yq)^2
~ ---------
2*(xp+yq)
In particular, as soon as (xp-yq)^2 is smaller or not much larger than
2*(xp+yq), then you will be able to guess xp+yq and hence guess p and q.
With your method, it may well be the case that 9p+15q will be close to
2*sqrt(135n), which is just as harmful as the case that p+q is close to
2*sqrt(n).
Jakob
"Michael Scott" <[EMAIL PROTECTED]> skrev i meddelandet
news:isPn6.37330$[EMAIL PROTECTED]...
> Its also good to keep p and q as far apart as possible.
>
> One way is to fix the top nibble of p as F and the top nibble of q as 9.
> This "F9" rule doesn't reveal anything of practical use for cryptanalysis
>
> Mike Scott
>
> "Mark Reed" <[EMAIL PROTECTED]> wrote in message
> news:2cGn6.56062$[EMAIL PROTECTED]...
> > Hi all !
> >
> > This is my first post (though you might say I'm a long time listener),
so
> > sorry if this has already been asked....
> >
> > In RSA key generation, 2 primes are found by getting random data and
> setting
> > the most and least significant bits are set to ensure the prime length
is
> > half the required modulus length and that it is odd. Then this is
> checked,
> > then the next candidate (say by adding two) until it is 'probably prime'
> > enough for use.
> >
> > If only the top bit is set, the key length may be one less than
required -
> > as an example for a 512 bit RSA key with
> > p = 0x80......
> > q = 0x80......
> >
> > then
> >
> > n = 0x40......
> >
> > My question is whether this is common practice, or if generally the top
> two
> > bits of each prime
> > (guaranteeing n > 0x90......)
> >
> > I suppose another possibility is that primes are generated until n is
the
> > required bitlength.
> >
> > Unless this method is used, isn't security compromised ? ie. n can be
> less
> > than the number of bits required or the top two bits of each prime are
> known
> > to be one.
> >
> > Thanks in advance,
> >
> > Mark.
> >
> >
>
>
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: philosophical question?
Date: Fri, 02 Mar 2001 10:38:05 -0600
wtshaw wrote:
> Randomness: To err is human; pseudorandomness: To air can be caused by beans.
>
> Computer randomness is to a hardware glitch as computer pseudorandomness
> is to a software bug.
>
> Machine randomness is to a squeak as machine pseudorandomness is to
> weaving lace; oil is to good design as bad programming is to ugliness.
:-) Air is also caused by bean counters, and I suspect that's more random
and ugly all at the same time.
Patience, persistence, truth,
Dr. mike
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
