Cryptography-Digest Digest #284, Volume #9 Thu, 25 Mar 99 13:13:03 EST
Contents:
Re: Crytpo Gurus - Please comment on this sceneario (Patrick Juola)
Re: RSA Algorithm ([EMAIL PROTECTED])
Re: RSA Algorithm (Michael Sierchio)
Re: compare RSA and D-Hellman ([EMAIL PROTECTED])
Re: Random Walk (R. Knauer)
Re: compare RSA and D-Hellman ("Sassa")
Re: Random Walk ("Sassa")
Re: Random Walk (Shawn Willden)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Crytpo Gurus - Please comment on this sceneario
Date: 25 Mar 1999 10:29:26 -0500
In article <[EMAIL PROTECTED]>,
Sundial Services <[EMAIL PROTECTED]> wrote:
>sb5309 wrote:
>>
>> I write this so as to learn something from your responses; if it is old
>> story, please don't flame me; I am a novice.
>> (I sent this two days earlier, but I did not see it in the group; so I
>> try again)
>>
>> Consider this scenario :
>>
>> Two persons are engaged to type, using computer keyboards, to produce a
>> series of numbers from 0 to 255. They are told that they should make
>> them random. These two series are later joined together to form a long
>> series.
>>
>> My comment
>> ----------
>> I don't really think that these two series will be random. Chance is
>> each series has its own bias, ie. biasness in one series is different
>> from the other.
>>
>> Can this be used in OTP ? My initial feeling is YES. As described by
>> David Kahn in "Codebreakers" (I quote this from the book "Decrypted
>> Secrets - Methods & Maxim in Cryptography" by F. L. Bauer), that the
>> Baudot code prepared by typists in WWII contained biases. For example, a
>> typist would typically place its left-hand small finger at 1 and the
>> thumb at 5, and the right-hand small finger at 6 and the thumb at 0. The
>> numbers so produced indicate that the digits from 1 to 5 would normally
>> form a number; so was 6 to 0. In other words, numbers like 10293, 28375
>> which required typing with fingers from each hand were not often
>> created. Numbers with triple and more similar digits were very rare.
>> Yet, as noted by David Kahn, the numbers did not have enough pattern for
>> crypto-attack.
>
>[ My right-hand is going to get very tired in that position ... ]
>
>I am certainly no "crypto guru," but I do suspect that "unpredictable"
>does not mean "random." I may type at a keyboard and the numbers I'd
>produce would be unpredictable but because of biases like the ones
>described they would not be random.
Well, "unpredictable" means something very close to "random," but
not "completely random." There's a certain degree of randomness
in what you type -- but it's not as random as a lottery ping-pong
ball generator, a fair roulette wheel, or a pair of dice.
The people who do the typing won't type with maximal randomness.
Fortunately, maximal randomness isn't necessary for an OTP to work
*in practice* unless you're R. Knauer; depending on how much your
typing diverges from complete and utter uniformity, there may not
be enough structure in the pads to permit a skilled cryptanalyst
to break it.
Or there may be, depending on just how skilled the cryptanalyst is
and how much text he has to work with.
-kitten
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA Algorithm
Date: Thu, 25 Mar 1999 15:19:41 GMT
In article <7dd1an$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> >I don't *think* this is a bad thing to do...
> Well, checking only eleven pairs, and picking one isn't going to be much worse
> than picking one pair at random. However, extremely low private exponents are
> known to be weak,
AMEN! Don't EVER use a private exponent that is less than N^(.29) where N
is the public modulus.
It is conjectured that .29 should be replaced with .5, but we have no proof
as yet.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: RSA Algorithm
Date: Thu, 25 Mar 1999 08:18:23 -0800
Reply-To: [EMAIL PROTECTED]
Scott Fluhrer wrote:
>... However, extremely low private exponents are
> known to be weak, so you probably don't want to do this with a billion pairs.
Usually the public exponent is "common" and small -- and usually a
Fermat prime, i.e. 3, 17 or 65537. This assures that the private
exponent is large, too.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: compare RSA and D-Hellman
Date: Thu, 25 Mar 1999 15:38:45 GMT
In article <7dc30r$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> In article <7dbvh5$5a9$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
stuff deleted, most of which was correct, except:
>
> A real reason for making A prime is to make the DLP harder: for composite A,
> all the attacker does is take the factorization of A
And if A is 1024 bits, (say) please explain how one achieves this
factorization?
The real reason for taking A prime is that we want the exponentiation to
take place in a cyclic group. i.e. it can be generated by just one element.
>, and solve the DLP for
> each component prime. This is a lot easier than solving the DLP for a
> similarly sized prime A.
Yes. If the factorization can be obtained. That is a big if.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 17:53:03 GMT
Reply-To: [EMAIL PROTECTED]
On 25 Mar 1999 10:09:28 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>It's a gamble.
Which in some instances is unacceptable.
If someone hired you to build a cryptosystem that could not be broken,
and threatened you with death if it did get broken, I suspect that
unless you are suicidal, you will not gamble.
>If you're completely risk-averse, then you won't
>accept *any* degree of uncertainty.
The problem is not in the willingness or unwillingness of accepting
any degree of uncertainty.
The problem is in accepting an unknown amount of uncertainty.
In fact, uncertainty by its very nature has no degree of certainty.
Using the term "degree" in conjunction with the term "uncertainty" is
oxymoronic. Either something is certain or it is uncertain, in the
latter case the fact that it is uncertain means you do not know
anything about it. Just because you can calculate the frequency of
occurance of something, and use the law of large numbers to arrive at
a "probability" of occurance does not mean that you have gained any
new knowledge about a given event.
Using the law of large numbers you can convince yourself that the
random walker should cross the origin many times as the number of
steps increases. Yet that is not the case (see Feller, op. cit.), and
the reason is that for finite sequences the law of large numbers is
only an approximation that does not give you any real knowledge about
the outcome of any particular random walk, unless you plan on
conducting an infinite number of them - in which case your frequency
interpretation of probability which comes from the law of large
numbers takes on meaning.
But we do not have the opportunity of conducting an infinite number of
trials, and even though the law of large numbers hints that the
expectation is in line with the frequency determined thus far does not
mean that the next occurance has to behave in any particular "normal"
fashion. As Feller points out for finite random walks, most paths are
far from "normal" - in fact most paths are downright abnormal.
>But this approach verges on the pathological;
If the risk is known and acceptable, then I would agree that it is
pathological to be overly concerned. But there are situations where
risk is unacceptable because the "degree of uncertainty" is unknowable
on an absolute basis. Saying that a woman has a probability p of
getting pregnant says nothing of merit for a particular woman you have
sex with, other than the obvious fact that there is always the
possibility she will get pregnant. Not knowing any more than the
probability p means that you do not know the "degree of uncertainty"
associated with any one or a series of sex acts with her. You just as
well flip a coin as try to determine a priori that she will get
pregnant or not based on some vague notion as the probability p.
Another example is that many people can drink alcoholic beverages and
drive. Some can even drink an amount that exceeds the state's
definition of DUI, which varies from 0.08 - 0.10 % blood alcohol
level. But just because YOU believe that you can drive safely at that
level does not mean you can do it with a "degree of certainty", even
if you have a glowing record of success from thousands of trials over
the years. There is always the possibility that you will get into an
accident that was significantly influenced by your blood alcohol
level.
The Looneytarians want all drug laws repealed based on the observation
that most people can function in society in a safe manner while under
the influence of certain drugs, even those considered "hard core" like
heroin and cocaine. And they are correct in that assessment - most
people can indeed function in society when using most drugs.
But the policy of a prudent society however is zero tolerance despite
the fact that the probability is small that drugs are detrimental to
the well-being of society. I suppose if you are a Looneytarian, you
would consider such a drug policy as "pathological", but that is just
a political judgement, not a rationall judgement.
Similarly, there are situations where zero tolerance for breaking a
cipher is prudent policy. Wouls be willing to "gamble" with the
Washington-Moscow hotline? I'm not, not even if it appears
"pathological" to people accustomed to gambling with their life.
>in practice, I can evaluate the risk of a
>new and heretofore unknown attack to be sufficiently small
>that I accept it.
I maintain that your evaluation is flawed if you rely on statistical
measures to make that determination. Saying that you have a
"probability" of not having your system cracked is just as foolish as
saying that the woman you last had sex with has a probablilty of
getting pregnant. A lot of consolation that is if she comes up
pregnant and you did not want that to happen.
>Hey, I occasionally cross streets against the
>light, too. Hasn't hurt me yet.
The operative word here is "yet".
There is always that unforseen circumstance which will result in your
becoming road kill. Therefore, the practice of putting yourself in
unecessary jepardy of serious injury or death is imprudent.
Bob Knauer
"The important thing is to stop lying to yourself. A man who lies
to himself, and believes his own lies, becomes unable to recognize
the truth, and he ends up losing respect for himself as well as for
others. When he has no respect for anyone, he yields to his impulses,
indulges in the lowest forms of pleasure, and behaves in the end like
an animal, in satisfying his vices."
--Dostoevsky (The Brothers Karamazov)
------------------------------
From: "Sassa" <[EMAIL PROTECTED]>
Subject: Re: compare RSA and D-Hellman
Date: Thu, 25 Mar 1999 17:04:29 +0200
Reply-To: [EMAIL PROTECTED]
hi
> Pick a large prime A, share that between the two people.
i suppose, A is not a secret? so if someone else knows it nothing harmful
happens? during following quadrillion years? ;)
> Person1 picks another large prime ( call it x ), that is relatively prime to A
> (note: if his private number x is prime then you need not check this).
> Person2 picks another large prime (call it y).
> Person one sends A^x and person two sends A^y. They both can now calculate
> A^(x*y).
i knew, algorithm is like this. but i was inclined to think that A, x, y and
N were random numbers with no restrictions?
i thought, i do not need to calculate any primes or to check for relative
primes, thus _much_ more easy to implement.
or if i choose some specific combination of non-prime A, x, y and N there's
some non-zero possibility to break it in a couple of days?
> If A is not prime you run into the chance of x mod A = 0.
what if x mod A == 0? sorry, i am not familiar with what modulus
algebra says upon this occasion :(
anyway, i can make x odd and less than A: just set the msb in A to 1, and
set msb in x to 0. to make x odd - just set lsb to 1 (odd, so it will always
be non-zero). thus x mod A will always be x!=0. anyway, i am using flat
pascal randomize routine, so it cannot generate 128 zero bytes at one time
;) (i was using that weak randomize routine for i was just going to make
sure DH works :))))).
btw, thanks to DJohn for expanding ECDH, etc for me...
--
Sassa
Apiary Inc.
______
@()(_)
/\\
[EMAIL PROTECTED]
------------------------------
From: "Sassa" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 17:11:23 +0200
Reply-To: [EMAIL PROTECTED]
> I used to believe what you are saying but have modified my position.
"...and due to fast change of arguers' positions, disputes became harder to
observe but shorter and saturated" ;)
--Zhvanetsky (The XX)
--
Sassa
Apiary Inc.
______
@()(_)
/\\
[EMAIL PROTECTED]
------------------------------
Date: Thu, 25 Mar 1999 09:43:01 -0700
From: Shawn Willden <[EMAIL PROTECTED]>
Subject: Re: Random Walk
"R. Knauer" wrote:
> >(1) Why are you using a random walk as the model for a random number
> >generation process?
>
> I am not. I have never proposed using the random walk as a model for
> crypto-grade random number generation.
So the random walk bit is a red herring?
> I am using the random walk as an example of how one can be deceived by
> naive intuition and a false belief in the vague notion of the "law of
> averages".
Someone who has thought a little about the properties of random walks in
particular would not be deceived by their intuition. The behavior of a random
walk is quite sensible when you remember that it has infinite memory. On the
other hand, someone who is applying intuition about memoryless processes (such
as a UBP) to a random walk will be deceived in much the same way that someone
applying their intuition about the carrying capacity of a truck to a sports car
will be decieved. It should not be surprising that a random, impromptu survey
of statisticians reveals a limited understanding of random walks. Outside of
the financial industry, the random walk is not a common model, and that's a
relatively new concept even in the financial industry.
> If the random walk fails that specification, then it is unsuitable for
> a TRNG.
Processes with memory are unsuitable for random number generation.
> The uniform one-dimensional random walk is the same as the uniform
> Bernoulli process in terms of how the bits of the sequence are
> generated.
Nonsense. The output of random walk looks nothing whatsoever like the output
of a UBP. A UBP can be used as the underlying random process on which one
builds a random walk, but the outputs of the two processes are radically
different. With this sort of construction, you must think of the random walk
as a sort of post processing on the underlying process.
> Do you have reasons why you think the UBP is not suitable to the
> generation of crypto-grade random numbers based on the specification
> above? If so, please let us know your considered thought based on
> concrete reasoning, with references too.
First, you're mixing things up. The uniform Bernoulli process is a model and
models are not suitable for generating anything. If the question is: Why is
the UBP not suitable as a model for a TRNG? then my answer is: I don't know.
Certainly a non-uniform Bernoulli process seems like an excellent model, since
it is then not necessary that p==q.
> I am not offering any arguments. I am merely quoting what I read in
> books.
Maybe I should post some passages from "Watership Down"? Come on, you must be
trying to accomplish something with your quotes. Generally quotations are used
to provide support in the form of expert opinion for arguments the poster is
making. I assume this is what you are doing, but I'm not seeing what your
argument is, or, more precisely, I see some arguments from you and some quotes
that you posted, but there is no obvious connection between the two. I'm
asking you to make that connection clear.
> In Li & Vitanyi, for example, I read several times that
> attempts to characterize random numbers, or the processes that
> generate them, with statisitical tests are futile. Even Kolmogorov
> himself chimes in with the same sort of comments.
Yes, randomness is a very subtle and complex concept, and, if I am interpeting
your use of the term "characterize" correctly, you are correct that it is
impossible to define statistical tests that will verify that a sequence is
random.
> The reason that I personally offered, which apparently you missed in
> my post the other day, is as follows. It is an accepted fact that one
> cannot generate random numbers algorithmically. But, if you could use
> algorithmic statistical tests to decide whether numbers were being
> produced randomly, then you could use those algorithms to generate
> random numbers, which contradicts the original premise.
Obviously. One cannot use statistical tests to detect randomness.
> The digit expansion of pi would make a good PRNG for that
> purpose because most of the output has the appearance of randomness
> according to statistical testing.
The expansion of pi might make a perfectly good PRNG, other than it's so much
slower than other, equally good methods. However, what does this have to do
with cryptography?
> My contention (based primarily on the comments of others) is that if I
> gave you the output of the expansions (not necessarily just the
> decimal expansion) of these transcendentals, you would consider them
> random based on statistical tests.
No I would not. I would consider them to uniformly distributed and free of
detectable bias. I might consider them to be unpredictable, but I would have
to believe that they may be predictable by someone who knows more than I do.
> That is, they have the *appearance* of randomness based on pseudo-random
> statistical tests.
Statistical tests do not and, as you pointed out, cannot characterize
randomness. Statistical tests do precisely what they're designed to do, which
is compute the probability that a particular finite string is produced by a
random variable that is distributed according to a particular model.
> The best specification for a crypto-grade random number generator that
> I am aware of is that it is capable of generating all possible finite
> sequences equiprobably, namely in an independent and equidistributed
> manner. With that specification for crypto-grade randomness, the
> cryptanalyst can have no reasonable certainty that the plaintext he
> has decrypted is the intended message, because it is just one possible
> plaintext out of a sample space of 2^N equiprobable plaintexts of
> length N.
(Assuming OTP encryption, you forgot to say).
Let me see if I can say this clearly:
If I have a coin that is weighted on one side, such that P(H) = .3 and P(T) =
.7 (as determined by experimental trial and statistical analysis of the
results, with sufficient trials to establish the required confidence level),
and I flip the coin and use it to generate bits, is the resulting stream
random? Yes, it is. It is heavily biased, but it is in fact random. Is it a
good RNG for cryptographic purposes? No. The biases disqualify it.
If I have a computer and an algorithm that generates a stream of bits with P(0)
= .5 and P(1) = .5 (always, as shown by a set of powerful statistical tests on
the results of a large number of trials), is this stream random? No, it is
not. Is it a good RNG for cryptographic purposes? Probably not. An attacker
may be able to discover the algorithm and predict the stream.
If I have a radio antenna that monitors noise from the stars and it just so
happens that the resulting bit stream has P(0)=.5 and P(1)=.5 (again, as
discovered through tests), is this stream random? Yes. Is it a good RNG for
cryptographic purposes? No. An attacker may be able to monitor the same
source.
If I have a noise-based RNG based on radioactive decay, well-shielded to
prevent an attacker from monitoring the output, and I have not performed any
statistical tests to look for, is this stream random? Yes, it is. Is it a
good RNG for cryptographic purposes? Possibly not. An attacker may be able to
detect significant biases in the output (possibly due to a feedback loop or
other bug).
If I do apply thorough statistical tests to my well-shielded,
radioisotope-based RNG and I discover that, with very high confidence, the
resulting bit streams fit a uniform distribution and evidence no memory, and I
then cease testing and put the RNG into production, is this stream random?
Yes, it is. Is it a good RNG for cryptographic purposes? Maybe. I might not
notice if it breaks and begins producing outputs that would fail my tests, and
an attacker might.
If I have my shielded, tested TRNG and while continuously monitoring the output
I notice a string of 100 consecutive zeros, is this stream random? No, it is
not. I don't care how carefully you designed and tested it, your TRNG is
broken. Is it a good RNG for cryptographic purposes? No.
Shawn.
------------------------------
** 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
******************************
