Cryptography-Digest Digest #745, Volume #11 Tue, 9 May 00 20:13:01 EDT
Contents:
Re: RSA (Anton Stiglic)
Re: Silly way of generating randm numbers? (Richard Heathfield)
Re: F function. (Mark Wooding)
Re: F function. (Tom St Denis)
Re: The RSA patent and my software (Paul Rubin)
Re: RSA (Tom St Denis)
Re: The RSA patent and my software (Tom St Denis)
Re: The RSA patent and my software (Paul Rubin)
Re: UK issue; How to determine if a file contains encrypted data? (Dan Day)
Re: Silly way of generating randm numbers? (John M. Gamble)
Re: More on Pi and randomness (Dan Day)
Re: Scary Possibility: Ticklish Chips (Dan Day)
Re: Question about iraqi block cipher (Dan Day)
Re: Question about iraqi block cipher (Tom St Denis)
Re: Database Password Brute Force Not Required (Dan Day)
m by n sboxes (Tom St Denis)
Re: GPS encryption turned off (Dan Day)
testing sbox system (Tom St Denis)
Re: GPS encryption turned off (Dan Day)
Re: GPS encryption turned off (Dan Day)
Re: Silly way of generating randm numbers? (Richard Heathfield)
Re: RSA (Bill Unruh)
Re: More on Pi and randomness (JCA)
Re: RSA (Bill Unruh)
Re: More on Pi and randomness (Gerry Myerson)
Re: Scary Possibility: Ticklish Chips (David A Molnar)
----------------------------------------------------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: RSA
Date: Tue, 09 May 2000 17:15:34 -0400
[EMAIL PROTECTED] wrote:
> Sorry, i think you missed my question, through my badd phrasing.
>
> 1.) Does RSA produce an evenly-distrubuted range of output values, (that
> looks random, but of course isn't.)?
>
> 2.) If this even distrubution caused by the many multiplications which
> form the single expondentiation procedure? I'll show what i mean:
I don't exactly know what you are looking for, but I could tell you
that the Jacoby symbol of an RSA plaintext can easily be computed
from it's ciphertext, thus RSA does not provide semantic security
(that is, RSA leaks some information about the plaintext it encrypts).
Anton
------------------------------
Date: Tue, 09 May 2000 22:25:18 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
"David C. Ullrich" wrote:
>
> On Wed, 03 May 2000 22:49:15 +0100, Richard Heathfield
> <[EMAIL PROTECTED]> wrote:
>
> >Julio César wrote:
> >>
> >> I dont know if this could help, but pi is in no way random.
> >>
> >
> >For a contrary viewpoint, see Knuth, TAOCP, Vol II, p41.
>
> Um, actually Knuth quotes Dr. Matrix as saying that
> mathematicians consider the digits of pi random - this
> shows just that Dr. Matrix does not know everything there
> is to know about what mathematicians think.
I'm sure he doesn't. I'm equally sure, however, that I.J.Matrix is in
fact Martin Gardner, who knows a thing or two about mathematics, does he
not?
Still, I'm not adamant about it. After all, I'm no mathematician. Pi
looks pretty random to me, but then the sea looks blue, so who am I to
judge?
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
35 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (62
to go)
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: F function.
Date: 9 May 2000 21:26:27 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> It is a bit. I did say it was *just about* low enough. Note that
> 14/256 < 2^-4. Iterated over 16 rounds (say), this is less than 2^-64.
> And yes I know that this is a long way from being a sufficient condition
> for security.
Dammit further. I got the sums wrong, I think. The best I can find for
any function of the form s(x) = ((x + c) mod 256)^k mod 257, with k odd,
is 16/256. I don't know where 14 came from.
This isn't really good enough. This was a bad idea.
-- [mdw]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: F function.
Date: Tue, 09 May 2000 21:44:13 GMT
Mark Wooding wrote:
>
> Mark Wooding <[EMAIL PROTECTED]> wrote:
>
> > It is a bit. I did say it was *just about* low enough. Note that
> > 14/256 < 2^-4. Iterated over 16 rounds (say), this is less than 2^-64.
> > And yes I know that this is a long way from being a sufficient condition
> > for security.
>
> Dammit further. I got the sums wrong, I think. The best I can find for
> any function of the form s(x) = ((x + c) mod 256)^k mod 257, with k odd,
> is 16/256. I don't know where 14 came from.
>
> This isn't really good enough. This was a bad idea.
No it wasn't. If you learned anything at all, it's a good idea.
BTW how are you messuring the diff probs?
Tom
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: The RSA patent and my software
Date: 9 May 2000 21:46:31 GMT
In article <[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>You guys seem to argue a bunch about it.
>
>I have chosen the mature way todo things is to not use RSA or any RSA
>ciphers until allowed.
>
>So basically I will not use RSA here or there until Sept 21st.
Um, it won't be allowed after Sept 21st either. Under Chinese law,
unauthorized cryptography of any kind can get you in a lot of trouble,
at least if you do it in China.
What? You don't care about Chinese law because you're in Canada not China?
Well, you're not in the US either, so why do you care about US patents
that aren't in force in Canada?
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RSA
Date: Tue, 09 May 2000 21:49:34 GMT
Bill Unruh wrote:
>
> In <8f9hkt$i8e$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
> ]In article <[EMAIL PROTECTED]>,
> ] Tom St Denis <[EMAIL PROTECTED]> wrote:
> ]> > Sorry, i think you missed my question, through my badd phrasing.
> ]> >
> ]> > 1.) Does RSA produce an evenly-distrubuted range of output values,
> ](that
> ]> > looks random, but of course isn't.)?
>
> Yes.
>
> ]>
> ]> Not really, it depends on what you are encrypting. Remember that the
> ]M
> ]> is the base, if the order of the group formed by using M as a base is
> ]> smaller/larger then for any other M then they will have statistical
> ]> biases in their sub-groups.
> ]>
> ]> For example 45 is a primitive generator mod 257, but 44 is not,
> ]compare
> ]> the two tables
> ]>
> ]> 45^x mod 257
> ]> 44^x mod 257
> ]>
> ]> To get a better idea.
>
> But this is irrelevant to his question. RSA does not take some number
> and raise it to an arbitrary power, it takes the message and raises it
> to a fixed power (e, which is 17 or 257 or whatever). Since there is an
> inverse, each M must map onto a unique other M. Ie the encryption is
> simply a permutation of the set of all messages. (Not quite, since if M
> is a multiple of p or q then you have problems, but these are a tiny
> subset of all possible messages-- of fractional order of 1/p + 1/q
> which is tiny.) The output of the encryption of any particular
> message will look random. Of course the output of a whole message need
> not be random at all. Eg, consider the message of all 1 ( 10^5 of them)
> Each block will cleary encrypt to the same output. Ie the output will be
> a bunch of blocks each the same. (each block being say 2000 bits long
> with a 2000 bit RSA key)
My point was just randomly doing
C = M^e mod n
For any M to produce a 'random' C output is a bad idea, since you will
get bias. Plus it's slow.
Maybe I misunderstood his post.
And the ciphertexts are not evenly distributed either. Just because the
function is invertible doesn't mean it's unbiased. Because you will
have sub-groups that do not share all possible outputs. Hence proving
my problem with using the output.
Which is why the RSA hash (as printed in Applied Crypto) is a bad idea,
Instead of doing
H = M^e mod n
(for e with unknown factorization of n)
Do
H = g^M mod n
n = prime (preferably p- prime too), and 'g' is a primitive root mod n.
Both are slow but the latter is balanced better.
Question: Could you chain the latter with
H[i] = g^(M + H[i - 1] mod (p - 1)) mod p
Or would that be a bad idea?
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: The RSA patent and my software
Date: Tue, 09 May 2000 21:51:17 GMT
Paul Rubin wrote:
>
> In article <[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >You guys seem to argue a bunch about it.
> >
> >I have chosen the mature way todo things is to not use RSA or any RSA
> >ciphers until allowed.
> >
> >So basically I will not use RSA here or there until Sept 21st.
>
> Um, it won't be allowed after Sept 21st either. Under Chinese law,
> unauthorized cryptography of any kind can get you in a lot of trouble,
> at least if you do it in China.
>
> What? You don't care about Chinese law because you're in Canada not China?
>
> Well, you're not in the US either, so why do you care about US patents
> that aren't in force in Canada?
You can get CryptoBag (with RSA PK) from my website at
http://www.tomstdenis.com/cb.html
I am just going to respect their patent and not push it in the US till
then.
BTW is anyone interested in helping work on this? I may have to stop
releasing CB in a bit and would like someone to take over.
Tom
--
Want your academic website listed on a free websearch engine? Then
please check out http://tomstdenis.n3.net/search.html, it's entirely
free
and there are no advertisements.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: The RSA patent and my software
Date: 9 May 2000 22:11:07 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>You can get CryptoBag (with RSA PK) from my website at
>http://www.tomstdenis.com/cb.html
>
>I am just going to respect their patent and not push it in the US till
>then.
Sounds like a good plan.
>BTW is anyone interested in helping work on this? I may have to stop
>releasing CB in a bit and would like someone to take over.
There are already so many other toolkits out there...
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: UK issue; How to determine if a file contains encrypted data?
Date: Tue, 09 May 2000 22:25:11 GMT
On Tue, 9 May 2000 20:03:36 +0100, "JoeC" <[EMAIL PROTECTED]>
wrote:
>If I was to hide a PGP or similar encrypted message within the least
>significant bits of a JPEG, and the normal PGP/whatever headers had been
>removed, is there any way to determine if that file contains encrypted data?
>Maybe through some sort of statistical or other determination of
>non-randomness?
Ironically, it's not "non-randomness" that's the tip-off, it's being
*too* random.
The low-order bits on image files, sound files, and so on may consist
mostly of noise, but it's noise with a definite "flavor" to it.
If you replace that with encrypted data, it'll look "pure random",
and that would be a clue that there's encrypted data there, and not
just "fuzz".
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED] (John M. Gamble)
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
Date: 9 May 2000 22:28:03 GMT
In article <[EMAIL PROTECTED]>,
Richard Heathfield <[EMAIL PROTECTED]> wrote:
>"David C. Ullrich" wrote:
>>
>> On Wed, 03 May 2000 22:49:15 +0100, Richard Heathfield
>> <[EMAIL PROTECTED]> wrote:
>>
>> >Julio César wrote:
>> >>
>> >> I dont know if this could help, but pi is in no way random.
>> >>
>> >
>> >For a contrary viewpoint, see Knuth, TAOCP, Vol II, p41.
>>
>> Um, actually Knuth quotes Dr. Matrix as saying that
>> mathematicians consider the digits of pi random - this
>> shows just that Dr. Matrix does not know everything there
>> is to know about what mathematicians think.
>
>I'm sure he doesn't. I'm equally sure, however, that I.J.Matrix is in
>fact Martin Gardner, who knows a thing or two about mathematics, does he
>not?
Dr. Matrix is Gardner's fictional character, charlatran, and all-around
rogue. Anything Gardner has Dr. Matrix saying must be taken with a
grain of salt, just after drinking the tequila.
-john
February 28 1997: Last day libraries could order catalogue cards
from the Library of Congress.
--
Pursuant to US Code, Title 47, Chapter 5, Subchapter II, '227,
any and all unsolicited commercial E-mail sent to this address
is subject to a download and archival fee in the amount of $500
US. E-mailing denotes acceptance of these terms.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Tue, 09 May 2000 22:30:43 GMT
On Tue, 09 May 2000 19:25:27 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>> To
>> put it in a different way: I wouldn't use the decimal expansions of
>> these two numbers
>> for cryptographic purposes, but I would certainly be tempted to do so
>> with Pi,
>> provided I can choose where to start in the expansion.
>>
>> Comments are welcome.
>
>Comments? OK, but you won't like it.
>
>Your proposal is cryptographically very weak.
>
>To see this is trivial. You propose a using a specific random string of
> digits. This is no better than using a pseudo-rng, but in your case the
>seed consists of the pair (pi, starting point). This is not a lot
>of entropy. In fact, it is very little.
In practice, yes. In theory, however (pi, starting point) could
have as much entropy as you wanted -- just start at the Nth digit,
where "N" itself is a number several hundred bits long...
Be careful how well you nail down your declarations...
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Scary Possibility: Ticklish Chips
Date: Tue, 09 May 2000 22:34:37 GMT
On Tue, 09 May 2000 08:09:15 +0000, Volker Hetzer
<[EMAIL PROTECTED]> wrote:
>Much easier. You design a chip. You give
>the design to a company for manufacturing.
>Manufacturer has connections to government
>and - your chip has an undocumented debug
>feature triggered by a certain combination on
>your 100+ pins or a specific fluctuation in the
>power supply.
This is one of the major things that caused
a huge distrust of the government's Clipper Chip
proposal. The chip was designed to be
"tamper proof" and "inspection proof", so there'd
be no way to tell *what* back doors had been
built into it...
And thus the reception for the chip was
"not only no, but hell no".
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Question about iraqi block cipher
Date: Tue, 09 May 2000 22:40:40 GMT
On 8 May 2000 12:52:35 -0700, [EMAIL PROTECTED] (David A.
Wagner) wrote:
>
>Is this _really_ an Iraqi standard, or is someone pulling our legs?
>
>It is a 5-round Feistel cipher, with a 256-bit block and with the same
>(complicated) Feistel function in each round. Thus, it should be
>vulnerable to slide attacks, if I am not mistaken. However, it looks
>like it may take 2^64 chosen texts to create a single slid pair.
Is there somewhere on the web that gives a semi-layman's intro
to "slide attacks"? (I've got a good math background, but
papers with too many crypto-specific buzzphrases tend to lose me,
for lack of introductory definitions.)
And how many "chosen texts" would it take to make a real dent in
Blowfish, which I believe is also a Feistel cipher?
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Question about iraqi block cipher
Date: Tue, 09 May 2000 22:59:32 GMT
Dan Day wrote:
>
> On 8 May 2000 12:52:35 -0700, [EMAIL PROTECTED] (David A.
> Wagner) wrote:
> >
> >Is this _really_ an Iraqi standard, or is someone pulling our legs?
> >
> >It is a 5-round Feistel cipher, with a 256-bit block and with the same
> >(complicated) Feistel function in each round. Thus, it should be
> >vulnerable to slide attacks, if I am not mistaken. However, it looks
> >like it may take 2^64 chosen texts to create a single slid pair.
>
> Is there somewhere on the web that gives a semi-layman's intro
> to "slide attacks"? (I've got a good math background, but
> papers with too many crypto-specific buzzphrases tend to lose me,
> for lack of introductory definitions.)
>
> And how many "chosen texts" would it take to make a real dent in
> Blowfish, which I believe is also a Feistel cipher?
>
It's my understanding the slide attack only works when all the round
functions are the same. You try to find pairs that match for certain
round numbers (a, b) (i.e for a pair) and deduce part of the key from
that.
However it's best to use round keys to avoid the attack.
Tom
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Database Password Brute Force Not Required
Date: Tue, 09 May 2000 23:00:10 GMT
On Fri, 5 May 2000 13:46:39 -0700, "John E. Kuslich"
<[EMAIL PROTECTED]> wrote:
>The password is a well chosen one and the only
>known method of password recovery for Word documents for Word 97 and beyond
>is brute force search.>
>
> [snip]
>
>CRAK Software quickly wrote up a program which recovered these passwords and
>allowed the database to be restored.
>The solution did not involve a brute force search but recovered the
>passwords instantaneously.
Please make up your mind.
>For details see CRAK Software http://www.crak.com
...where you'll find that the "details" will cost you $29...
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: m by n sboxes
Date: Tue, 09 May 2000 23:14:14 GMT
I updated my sboxgen program to allow unique/non-unique sboxes when the
input size is greater then the output size. For example in the DES 6x4
sboxes there are basically four rows of 4x4 sboxes. Well now I just
have an array of (in this example) 64 entries labeled 0..15 in no
particular order (i.e you could have 15 twice in the same row).
Questions:
1. Is this generally a bad idea? (I still test the sboxes for the
various qualities....)
2. Will the WT still give valid results? I think it will, but I want
to be sure.
The code is at
http://www.tomstdenis.com/sboxgen.c
I think by doing compressions this way they can be less uniform...
Tom
--
Want your academic website listed on a free websearch engine? Then
please check out http://tomstdenis.n3.net/search.html, it's entirely
free
and there are no advertisements.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Crossposted-To: sci.geo.satellite-nav
Subject: Re: GPS encryption turned off
Date: Tue, 09 May 2000 23:22:16 GMT
On Fri, 05 May 2000 20:56:28 -0400, Martin Grossman <[EMAIL PROTECTED]> wrote:
>Third...there are many many ways of making secure devices tamper proof
> that most people wouldn't even think of!
Any hints? This sounds fascinating.
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: testing sbox system
Date: Tue, 09 May 2000 23:26:43 GMT
Say I use four sboxes in parallel, what is a way to measure the
independance between the other sboxes... I was thinking like
(four 8x8 sboxes...)
for x = 0 to 256
sbox[4][x] = sbox[0][x] xor sbox[1][x] xor sbox[2][x] xor sbox[3][x]
Then test for ideal non-linearness (as supplied by the user), SAC and
BIC?
I am thinking of adding this test to sboxgen...
Tom
--
Want your academic website listed on a free websearch engine? Then
please check out http://tomstdenis.n3.net/search.html, it's entirely
free
and there are no advertisements.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: GPS encryption turned off
Date: Tue, 09 May 2000 23:28:05 GMT
On 5 May 2000 22:53:32 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>Mike Andrews <[EMAIL PROTECTED]> wrote:
>>The SPS (public and unclassified) signal is used by the military
>>GPS boxes to synchronize to the P(Y) signal. Unless there is
>>something new that I'm unaware of, a military GPS _can't_ sync up
>>in precision mode without the SPS signal.
>
>They can now. That's the new development that allowed them to turn
>off SA. It means they can jam the SPS signal and military receivers
>will still work.
How did they accomplish that?
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: GPS encryption turned off
Date: Tue, 09 May 2000 23:28:55 GMT
On 3 May 2000 16:20:39 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>Paul Koning <[EMAIL PROTECTED]> wrote:
>>Interestingly enough, SA has been turned off before. For example,
>>during the Gulf War, so the US military could use commercial off the
>>shelf GPS units and get good accuracy. (Apparently they couldn't get
>>enough P/Y units.)
>
>The Gulf War was before GPS was declared fully operational. The
>military has plenty of P/Y units now. (Yes I know about the Warthog
>incident in 1997 too, but that was of very brief duration, unannounced,
>and until recently, officially unconfirmed).
What was "the Warthog incident"?
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
Date: Wed, 10 May 2000 00:29:35 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Silly way of generating randm numbers?
"John M. Gamble" wrote:
>
> In article <[EMAIL PROTECTED]>,
> Richard Heathfield <[EMAIL PROTECTED]> wrote:
> >"David C. Ullrich" wrote:
> >>
> >> On Wed, 03 May 2000 22:49:15 +0100, Richard Heathfield
> >> <[EMAIL PROTECTED]> wrote:
> >>
> >> >Julio César wrote:
> >> >>
> >> >> I dont know if this could help, but pi is in no way random.
> >> >>
> >> >
> >> >For a contrary viewpoint, see Knuth, TAOCP, Vol II, p41.
> >>
> >> Um, actually Knuth quotes Dr. Matrix as saying that
> >> mathematicians consider the digits of pi random - this
> >> shows just that Dr. Matrix does not know everything there
> >> is to know about what mathematicians think.
> >
> >I'm sure he doesn't. I'm equally sure, however, that I.J.Matrix is in
> >fact Martin Gardner, who knows a thing or two about mathematics, does he
> >not?
>
> Dr. Matrix is Gardner's fictional character, charlatran, and all-around
> rogue. Anything Gardner has Dr. Matrix saying must be taken with a
> grain of salt, just after drinking the tequila.
>
Ah, I didn't know that. Knowing a little of Mr Gardner's work, however,
I can well believe it. I therefore stand thoroughly corrected.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
35 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (62
to go)
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA
Date: 9 May 2000 23:39:35 GMT
In <[EMAIL PROTECTED]> Anton Stiglic <[EMAIL PROTECTED]> writes:
>I don't exactly know what you are looking for, but I could tell you
>that the Jacoby symbol of an RSA plaintext can easily be computed
>from it's ciphertext, thus RSA does not provide semantic security
>(that is, RSA leaks some information about the plaintext it encrypts).
What is the Jacoby symbol of text?
------------------------------
From: JCA <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Tue, 09 May 2000 16:29:34 -0700
Actually, the comments I meant to elicit were those having to do
with the relationship between the normal character of a number (what
the heck is this called? Normality? Does anybody know?) and randomness
criteria.
Thus, Champernowne's number is normal but its decimal expansion is
trivially predictable, no matter where in the expansion you may be, because
of the way in which it is constructed. On the other hand, if I tell you the
decimal
in position N in the expansion of Pi you won't be able to tell me anything
about
the following decimal sequence short of doing the computation yourself.
I wasn't anyway proposing to use raw Pi as a source of random numbers,
pretty
much for the reason you present (although if one could start computing
decimals
of Pi at any arbitrary position in its expansion in a fast, practical way,
things might
be slightly different.) A few days ago I was thinking aloud about a
variation of this,
consisting of introducing deliberate arithmetic mistakes, a la Shanks, in
the calculation
of Pi. This would do away, in principle, with the core of your objection;
but it is not all
clear to me that the resulting string should necessarily have good
randomness properties.
Bob Silverman wrote:
> In article <[EMAIL PROTECTED]>,
> JCA <[EMAIL PROTECTED]> wrote:
> >
> <snip>
>
> > To
> > put it in a different way: I wouldn't use the decimal expansions of
> > these two numbers
> > for cryptographic purposes, but I would certainly be tempted to do so
> > with Pi,
> > provided I can choose where to start in the expansion.
> >
> > Comments are welcome.
>
> Comments? OK, but you won't like it.
>
> Your proposal is cryptographically very weak.
>
> To see this is trivial. You propose a using a specific random string of
> digits. This is no better than using a pseudo-rng, but in your case the
> seed consists of the pair (pi, starting point). This is not a lot
> of entropy. In fact, it is very little.
>
> Using *named* transcendental constants is not cryptographically
> useful. There are not enough of them and whichever you select is easily
> guessed.
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: RSA
Date: 9 May 2000 23:44:17 GMT
In <[EMAIL PROTECTED]> Tom St Denis <[EMAIL PROTECTED]> writes:
>My point was just randomly doing
>C = M^e mod n
>For any M to produce a 'random' C output is a bad idea, since you will
>get bias. Plus it's slow.
If it is random M then no the output is equally random. If you fix M and
vary e than your comment it appropriate. Fixing e and varying M however
the bias is very non-obvious. If you claim that say English text will
produce biased output, then your claim would be stronger. But I dubt
anything is known there.
>Maybe I misunderstood his post.
>And the ciphertexts are not evenly distributed either. Just because the
>function is invertible doesn't mean it's unbiased. Because you will
Yes, it does. It cannot be "biased" and be invertible, unless the input
is also "biased". Over all imputs the identity permutation is unbiased
as well.
>have sub-groups that do not share all possible outputs. Hence proving
>my problem with using the output.
What is the group operation to which your refer?
>Which is why the RSA hash (as printed in Applied Crypto) is a bad idea,
>Instead of doing
>H = M^e mod n
>(for e with unknown factorization of n)
>Do
>H = g^M mod n
>n = prime (preferably p- prime too), and 'g' is a primitive root mod n.
>Both are slow but the latter is balanced better.
>Question: Could you chain the latter with
>H[i] = g^(M + H[i - 1] mod (p - 1)) mod p
>Or would that be a bad idea?
>Tom
------------------------------
From: Gerry Myerson <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: More on Pi and randomness
Date: Wed, 10 May 2000 09:45:00 +1000
In article <[EMAIL PROTECTED]>, JCA
<[EMAIL PROTECTED]> wrote:
=> Something that is not clear to me is how to tie down normalcy
=> (normalness? normality?) to randomness. So, although the decimal
=> expansion of Pi (not proven yet to be normal) looks attractive in
=> this respect, those of Champernowne and Copelan-Erdos numbers
=> (which are known to be normal to base 10) do not. To put it in a
=> different way: I wouldn't use the decimal expansions of these two
=> numbers for cryptographic purposes, but I would certainly be
=> tempted to do so with Pi, provided I can choose where to start in
=> the expansion.
If you get to choose where you start in the expansion, chances are
that pi & Champernowne are indistinguishable.
Gerry Myerson ([EMAIL PROTECTED])
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Scary Possibility: Ticklish Chips
Date: 9 May 2000 23:41:26 GMT
Dan Day <[EMAIL PROTECTED]> wrote:
> be no way to tell *what* back doors had been
> built into it...
> And thus the reception for the chip was
> "not only no, but hell no".
My favorite paper of last week :
A. Young, M. Yung, "The Dark Side of Black-Box Cryptography -or-
Should We Trust Capstone?", CRYPTO '96, pp 89-103, Springer-Verlag
http://www.cs.columbia.edu/~ayoung/crypto96.ps
Be afraid of black-box crypto. Be very afraid.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
