Cryptography-Digest Digest #345, Volume #9 Tue, 6 Apr 99 03:13:03 EDT
Contents:
Re: Special Case of RSA (Ted Kaliszewski)
Re: Special Case of RSA (Boris Kazak)
Re: Tripple DES key length. (David Miller)
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers (Jerry Coffin)
Re: True Randomness & The Law Of Large Numbers ("Franzen")
Re: True Randomness & The Law Of Large Numbers ([EMAIL PROTECTED])
Re: IDEA (Boris Kazak)
----------------------------------------------------------------------------
From: Ted Kaliszewski <[EMAIL PROTECTED]>
Subject: Re: Special Case of RSA
Date: Mon, 5 Apr 99 21:28:32 -0500
Look up an article by G.R. Blakley and I.Borosh in Comp.&Math. with Appls.
1979, pp.169-178 for details pertaining to this problem. Also, by Donald R.
Smisth and James T Palmer in Mathematika, 1979, pp.44-52. It is a tough
problem not readily utilized in breaking the cryptosystem in question.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Special Case of RSA
Date: Mon, 05 Apr 1999 18:11:05 -0400
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
>
> Hello,
>
> I am currently doing some research on RSA algorithm and I found a
> problem that I'm sure has been discussed before...
>
> I am interested in some info/links/references or ideas on a case of
> RSA when we have: x^e mod N = x (i.e. encrypted message is the same
> as the original message...) Does anyone have any references about the
> study of this particular case? Also, any idea how to calculate the
> probability of this occuring?
>
> Thank you very much!
>
> Jenny Stevens, UNC
> [EMAIL PROTECTED]
>
====================
First, the situation is rather unlikely, the probability of this
happening is vanishingly small.
For such a thing to happen, "e-1" must be equal to (or a multiple of)
the period generated by "x" in the field (1,N-1). To compute the
period, it is necessary to know the factoring of N in prime numbers,
say N = P1*P2*P3... (in RSA case there are only P1 and P2).
Then the maximum period which is possible in this (1,N-1) field will
be the lowest common multiple of (P1-1),(P2-1),(P3-1),...
For example, if N = 2^32-1 = 3*5*17*257*65537, the maximum period
is 65536. So taking any number relatively prime to 2^32-1 and raising
it to the power 65536, you get a guaranteed 1, next multiplication will
produce your original number. BTW, this is one of the methods of
computing the multiplicative inverses, you raise your number to the
power of (PeriodLength - 1).
Returning to the RSA case, the two constituent primes are of the
order of 500-700 bits long, they are selected so that the period
generated by multiplications is also of the order 2^500 or more, so
that randomly picking up a number you practically have a 2^-500
probability of hitting precisely the (period+1) value.
Hope this helps BNK
------------------------------
From: [EMAIL PROTECTED] (David Miller)
Subject: Re: Tripple DES key length.
Date: Tue, 06 Apr 1999 01:32:20 GMT
Patrick Juola ([EMAIL PROTECTED]) wrote:
: In article <7dongn$gto$[EMAIL PROTECTED]>,
: Mickey McInnis <[EMAIL PROTECTED]> wrote:
: >In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
:(DJohn37050) writes:
: >|> ...
: >
: >I think it's a bit of an overstatement to refer to a meet-in-the-middle
: >attack as if it is practical. The storage of 2**56 trial runs, and/or
: >searching through 2**56 trials to compare against makes
: >it highly impractical to actually do a meet-in-the-middle attack.
: >
: >Or is there some implementation of a meet-in-the-middle attack
: >against even 2-DES that doesn't involve (2**56)+ storage elements?
: >That's 512 Million Gigabytes, if you store 64 bits per trial.
:
: This is frighteningly close to practical, however.
:
: A farm of writable CD-Rs runs about $2/gig, retail. Cut that
: down to $1/gig, wholesale, and you're looking at only about 500M
: dollars to store that many elements. That's certainly inside
: a government budget, and might even be doable in a large corporation.
Uhmm, hold on a second there partner...
At the rate of 600 MB/platter you're looking at something on the order
of 800 million CD.
If you wrote a megabyte per second, you're talking about 800 million
seconds to write them all - that's about 25 years. Divide by 1000
cd writes, each of them able to write a MB/s and you're down to about
10 days, which would seem a bit more reasonable. Maybe.
If you were to take the 800 million CD's and stack them up, and they
were about 10 to the inch, you'd have a stack 1,262 MILES high.
Of course, this only gives one a single block of plaintext with all
possible keys. Better hope your target contains one such block!
Bear in mind that to be used in an attack one would either have to sort
2^56 elements and store them back into the 800 million CD's or search
sequentially through all of them to find if the key tested from the
other end to one which you have. I'm quite sure that reading all 800
million for each test is impracticle, even 1000 at a time, so we'd have
to consider how long it would take to sort 2^56 elements. I'll defer
to someone else on that count.
We neglected to mention the problem is only half as bad as stated above:
because of the inverse key aspect of DES we'd only have to store 2^55
64 bit blocks. This would, of course, make the sort much easier:)
In short, storage of the blocks is only a piece of the whole problem,
and it looks to me like the MITM attack on 2DES is a ways from being
practical.
--- David Miller
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 06 Apr 1999 03:00:36 GMT
"R. Knauer" wrote:
> On Mon, 05 Apr 1999 07:35:31 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
> >> Yes, it holds for *most* distributions. But it does not hold for
> >> distributions that are not square integrable.
> >So what? No meaningful situation is going to have infinite energy.
> QED has infinite energies. Yeah, renormalization dealt with them, but
> nobody considers that scheme to be fundamentally correct.
And all the competent theorists realized that that indicated a flaw
in QED. And it is well-known that the infinities cannot be
"renormalized" away in similar theories of other some interactions.
That is one of the main motivations behind later alternate
fundamental theories.
But you are dodging the admission that my "So what?" is valid.
Non-square-integrability is not an excuse.
> >> >If it is supposed to output uniformly
> >> >random bits, and the r.v. X is the value of a generated bit, then
> >> >X has mean 0.5 and s.d. 0.5.
> >> Prove that. But be careful about your assumptions, because if you go
> >> off into classical statistical theory you will miss the mark.
> >That's an elementary exercise for the beginning statistics
> >student.
> Yeah, one of those "back of the envelope" calculations.
> >I suggest *you* work out the proof; it might be an
> >opportunity to practice converting "word problems" into formal
> >specification, after which computation of the answer is easy.
> Here is an envelope - you work it out. You are the one making the
> assertion.
I obviously have already worked it out, and yes, it can be done
on the back of a very small envelope. The point is, you don't
know how, and refuse to learn, yet feel entitled to criticize
the very technology that you don't understand. Why?
> >That's for sure, but only because it makes no sense.
> >Here are some finite numbers:
> > 42
> > 0
> > 1234566778901033909867041675
> > -72
> Those are integers and are part of the ensemble of random numbers.
> >Here are some others:
> > 0.3
> > Pi
> > 23/41
> > -238408965034.7235876134
> > 1-e
> >If these are what is meant in your "spec", then TRNGs cannot
> >exist.
> You know better than that (I presume). The sequences that are
> generated by a TRNG are integers. Pi is not an integer, and neither
> are any of the other real numbers above. <jeez>
> >What would "equidistribution" mean?
> Fer chrissakes, you are being deliberately obtuse.
No, now that you have clarified that you mean just the integers
(and apparent allow negative integers, although the same problem
occurs either way), the question stands. It is a serious point.
> Equidistribution means that the sample space has a flat distribution.
That isn't very precise, but what I suppose you mean is that the
TRNG has the same chance of generating
42
as of generating
1234566778901033909867041675
In which case, there is practical certainty (measure 1) that the
*first* number ever generated by any actual "TRNG" (if it could
exist) would be too large to be represented in whatever equipment
realized the TRNG.
So there is something wrong with your definition. Others have
attempted to substitute workable definitions, in order to make
*some* sense out of your "TRNG" concept.
> >For that matter,
> >what would "independent" mean if, as you claim, it is not
> >the standard probabilistic meaning for this term?
> Independent refers to the selection process, not the distribution.
And what does "independent" mean in *that* context, if not
related to the usual statistical meaning?
> >I took the liberty of *stating* the specific property that a
> >*meaningful* specification might include (outputting uniformly
> >random bits), which I used to compute the parameters that you
> >requested.
> Parametric tests are not applicable to testing true randomness or lack
> of true randomness.
> >If your TRNG isn't supposed to include at least
> >*that* property among whatever else it is, then "True Random"
> >is certainly a misnomer.
> True Random can be stated in an absolute manner. It is the process
> which produces true random numbers like a quantum computer programmed
> to calculate true random numbers.
If you have a specific design in mind (perhaps borrowed from a
book you read), then that's pretty "absolute". We *know* what
statistics result from application of QM (at least, the standard
theory used in work on "quantum computing") in various situations,
so given a specific design, we can in principle derive the model
for the distribution it generates. In fact, this is done all
the time in physics laboratories everywhere. For example, in
PAC work I was involved with, the model turned out to be a sinusoid
imposed on a decaying exponential, convolved with the response of
the sampling equipment. The basis of the phenomenon was photon
pair correlation from a certain radioactive decay. Just because
the root phenomenon is fundamentally "quantum" doesn't mean that
statistics is inapplicable, as you seem to have been arguing.
> Such processes are truly random only by virtue of the underlying
> quantum processes characterize them. Classical chaotic systems may be
> exceedingly random to a level that cannot be distinguished from true
> randomness, but they are still not truly random. Only quantum
> processes are truly random.
If it walks like a duck, quacks like a duck, and looks like a
duck, then it's a duck, for all practical purposes. Or are you
making a distinction without a difference?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 06 Apr 1999 03:10:10 GMT
"R. Knauer" wrote:
> There is nothing wrong with those attributions above. Anyone who has
> been on Usenet for any length of time knows that the attributions
> above clearly point to me as the author of that statement.
And any *thoughtful* person who has been involved with the network
newsgroups understands that an attribution to someone whose words
*are not cited at all* is inappropriate and should have been omitted.
Just as I omitted any attribution to Rubin in the above citation.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 06 Apr 1999 03:06:42 GMT
"R. Knauer" wrote:
> More bluster and pontification - and a clear demonstration that you
> are completely full of bullcrap.
Far from it -- in fact I explained how it was done to a fellow
who asked politely via e-mail. I'm sure Gillogly, Reed, and
others who have actually practiced cryptanalysis understand
the methodology, also. It illustrates why OTP is not used in
very many actual cryptosystems, despite its theoretical
properties having been well understood since before WWII.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Mon, 5 Apr 1999 23:16:47 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Therefore, it a RNG fails those statistical tests, it is reasonably
> certain that it is not random, and if it does not fail those tests, it
> is reasonably certain that it is random. If you claim that there is a
> third set of maybe/maybe-not, then there can be no set of TRNGs that
> are reasonably certain to be non-random.
A test of a random number generator can never be an absolute thing.
You can NEVER say that failing a particular test means a generator is
not random. A generator that could NOT generate a failing sequence of
numbers would, by that very fact, be provably non-random.
To give an example: if I feed a string of 100 1's to a test of a
random number generator, I think it's safe to say that NO test would
pass this as a random sequence. Despite this, a truly random
generator must be EXACTLY as likely to produce this particular
sequence of numbers as ANY other sequence of the same length. If it's
not, we can predict that it's less likely to do so, and the output is
now predictable rather than entirely random.
------------------------------
From: "Franzen" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 6 Apr 1999 00:51:02 -0500
Bob Knauer <[EMAIL PROTECTED]> posted the following extracts Apr
1, 1999 at 4:34 PM in response to my previous posting:
---
>I would ask what are you using for the TRNG sequence in that test.
>IOW, you must be comparing a purported TRNG to a known TRNG. What is
>that known TRNG?
The fair flipping of a two-sided coin is one. It matches most closely
the kind of TRNG process I think underlys most of your recent postings
in this newsgroup.
---
>>First you state statistical tests cannot distinguish uniform randomness
>>from pseudo-randomness (first paragraph above). Now you parenthetically
>>state some PRNG's can generate "close to" uniformly random sequences.
>>How can you possibly know? Not only would you have to be able to
>>distinguish between the two randomness potentials, but you would also
>>have to have a way to measure them with some degree(s) of precision.
>
>You evidently were not here when we discussed that issue.
I am here now. I am asking you about the discrepancy in your two
statements. The "we" must be you and some other person(s); my not being
"here" excludes me from this particular "we."
The rest of your words answering my original posting do not pertain to
my above extracted discrepancy statement to you. I would appreciate a
responsive answer from you, or none at all.
---
>We all realize that it is impossible to build a classical TRNG that is 100%
>random.
What the devil is a "classical" TRNG?
100% random? That implies 99, 98, ... . Are you one of those who think there
exists some sort of uniform randomness acme. I currently think there is
uniform randomness, or not uniform randomness: Nere the twain shall meet.
That PRNG and TRNG processes can somehow merge does not compute at all in
my experience or possibilities thinking.
I think of uniform randomness as concurrently "perfectly imperfect"and
"imperfectly perfect."
---
>There will always be flaws which disturb the process and give
>it some small amount of non-randomness, such as slight 1-bit bias.
So your hypothetical TRNG will "always" be flawed. I am not very encouraged
by this part of your vision.
Just what is 1-bit bias in your view? Most of the concepts you present as
parts of your current position I can visualize; your bias concept I cannot.
---
>Doesn't anyone realize that if you could model true randomness with
>mathmatical objects, that you could solve some of the mysteries of
>quantum mechanics.
I think taking the mystery out of uniform randomness can change the current
view of "truth" in many unimaginable ways. That may be a QM layman (non-TM)
equivalent to what you say; or maybe not. I will let you decide.
---
Douglas McLean
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Tue, 06 Apr 1999 06:10:31 GMT
Bob Knauer had written:
: Yet people still insist that if their pet RNG
: passes such and such a statistical test, it is truly random.
: Hell, the famous FIPS-140 says that. Have you ever read FIPS-140?
Bryan G. Olson responded:
> >Can you quote where FIPS-140 says that? Note that saying to
> >reject a generator that fails statistical tests is not the
> >same thing.
[EMAIL PROTECTED] wrote:
> I claim that there are only two valid sets for randomness:
>
> Set #1: Reasonable certainty that the process is not random;
>
> Set #2: Processed which do not exist in set #1.
[...]
> There is no middle set of RNGs that are maybe random, maybe not random
> on the basis of reasonable certainty.
There is set #2. Where does FIPS-140 say that sources in set
#2 are truly random?
> Therefore, it a RNG fails those statistical tests, it is reasonably
> certain that it is not random, and if it does not fail those tests, it
> is reasonably certain that it is random.
Uh, that's you claiming what you said FIPS-140 claims.
> If you claim that there is a
> third set of maybe/maybe-not, then there can be no set of TRNGs that
> are reasonably certain to be non-random.
I'm saying that membership in set #2 does not imply a generator
is truly random. Does FIPS-140 say otherwise?
> You can't have it both ways. Either a TRNG can be determined to be
> non-random, in which case there is no set of maybe/maybe-not random
> TRNGs, or the opposite is the case and then your tests are worthless.
We can have it the way it is. If the facts are inconsistent with
the theory, then the theory is wrong. If the facts are consistent
with the theory, then the theory remains plausible.
I challenged you to quote FIPS-140 where it says what you claimed
it says, as re-included at the top. A reasonable response would
include text from FIPS-140, or a retraction. I am not asking you
to quote yourself.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: IDEA
Date: Mon, 05 Apr 1999 21:46:25 -0400
Reply-To: [EMAIL PROTECTED]
Martin Thiim wrote:
>
> Hi,
>
> can anyone tell me where I can find a document (preferably on the net) with
> the standards on IDEA encryption. I want to make my own IDEA encryption
> program, but I don't know much about the algorithm.
>
> Thanks,
> Martin
===============
Try < http://www.rpini.com > and browse their Crypto CD online.
You will find C programs in /source/ciphers/.
The site is in Switzerland.
Best wishes BNK
------------------------------
** 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
******************************
