Cryptography-Digest Digest #967, Volume #10 Mon, 24 Jan 00 16:13:01 EST
Contents:
Re: How much random needed for random (Eric Murray)
Re: newbie question: symmetric versus asymmetric (wtshaw)
Re: MIRDEK: more fun with playing cards. (Paul Rubin)
Re: how to break 1timepads with the same pad used N times ("Tony T. Warnock")
Re: Reversibly combining two bytes? ("Tony T. Warnock")
Re: LSFR (Mike Rosing)
Weierstrass Normal Form (Laura Feinstein)
Re: generating "safe primes" ("Michael Scott")
Re: generating "safe primes" (Bob Silverman)
Re: Weierstrass Normal Form (John Savard)
Re: How much random needed for random (Eric Lee Green)
Re: Weierstrass Normal Form (Mike Rosing)
Re: Weierstrass Normal Form (John Savard)
Re: Calculating A^-1 Mod P (Paul Schlyter)
Re: Twofish question (ciphertext chaining) (David Wagner)
Re: LSFR (David Wagner)
Re: How much random needed for random (Tim Tyler)
Re: MIRDEK: more fun with playing cards. ("r.e.s.")
Re: MIRDEK: more fun with playing cards. ("r.e.s.")
----------------------------------------------------------------------------
Subject: Re: How much random needed for random
From: [EMAIL PROTECTED] (Eric Murray)
Date: 24 Jan 2000 10:16:14 -0800
In article <[EMAIL PROTECTED]>,
Scott Nelson <[EMAIL PROTECTED]> wrote:
>On Sun, 23 Jan 2000 11:59:15 +0200, "Yoni M." <[EMAIL PROTECTED]> wrote:
>
>>I'm using SecureRandom (java) in my SSL implementation to produce the
>>random bytes needed for the challanges. My problem is performance, it
>>takes too long to generate the bytes. If I'm using a simple Random
>>everything is much faster.
>
>If your problem is performance, then you should consider
>a language built for performance, rather than compatibility.
>Java is nice for some things, but this isn't one of them.
>
>>Can I initialize the secure random with the current time (long), or
>>isn't it enough ?
>No, it's not enough. If you want to build a secure rng,
>then read the Yarrow page http://www.counterpane.com/yarrow.html
>It discusses this, and many other pitfalls.
>
>>This way is much faster than initializing the
>>SecureRandom without any seed.
>Faster yes, but not secure.
>
>>Does anyone knows of a short cut or suggestion how to improve the
>>performance without reducing security ?
>>
>Not in Java.
>Normally, you can speed initialization by keeping a pool
>of entropy handy which is then hashed for use. That implies
>the ability to write files, which is counter to the Java
>philosophy. (and introduces another whole host of problems.)
>For your app, this would probably need to be a separate program.
If he's on Linux or Solaris, he could use the built-in system
entropy pool /dev/random. That would require only the ability to
do read()s outside the sandbox, which I beleive is allowed
in the default security model. /dev/random is probably supported
on more platforms now.
BTW the original SSL random-number break (sorry I can't remeber the
authors names at the moment) was against netscape's SSL implementation
which used time + process id as the seed to one of the Unix rand()
functions. Not only is the rand() function not of cryptographic quality,
but the guys who did the break found that it was easy to find the
seed values.
--
Eric Murray www.lne.com/~ericm ericm at the site lne.com PGP keyid:E03F65E5
<IMG LOWSRC="javascript:alert('Delete C: and install Linux?')">
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: newbie question: symmetric versus asymmetric
Date: Mon, 24 Jan 2000 12:54:44 -0600
In article <newscache$3uduof$tmn$[EMAIL PROTECTED]>, "dee"
<[EMAIL PROTECTED]> wrote:
> What essential differences between asymmetric key and symmetric
> key crypto-protocols, including tamper evident hardware, when is
> it neccessary to support revocation of stolen keys?
Some are probably not so glad to see me answer your post, as I see
asymmetric and symmetric being best descriptive of other attributes than
whether a public key is involved. If you rephase your question to be
conventional vs. public-key encryption, I will settle for that.
Private shared keys for convention encryuption are the strict business of
those who have them, and the protocols for such things are limited only by
the imaginations of those involved. Structures that rely on companies
and/or government are not apt to be with people you really know: in
matters of trust with strangers, if you see no option than to play with
their rules, you have indicated your inability to take charge of matters
yourself.
The cry is that it all works. Not necessarily. Computer security is a
massive problem that is not easily patched. All coexisting hype will not
make the myrid of compounded problems, including potential balls and cups
key management, go away. But, as Johnny used to say, "You buy the premise,
you buy the bit."
--
As an issue in the campaigns, crypto may be forgotten unless we
ask questions whenever we can to bring it up. Report responses.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: MIRDEK: more fun with playing cards.
Date: 24 Jan 2000 18:26:26 GMT
In article <[EMAIL PROTECTED]>,
Paul Crowley <[EMAIL PROTECTED]> wrote:
>It's not a downside that necessarily applies to randomised stream
>ciphers where the randomiser is sent along with the message; this is
>true of Mirdek, and we've heard some ideas about how that could be
>done for ARC4-52 and ARC4-Rubin (the CRT-based variant).
Um, I don't think there's such a thing as "ARC4-Rubin". The CRT thing
is just a different way of physically/mentally manipulating the cards
that's supposed to be a little easier. The cipher itself is supposed
to be exactly the same, for cryptanalysis purposes. You could think
of it as being like changing the initial and final permutations in
DES. They don't have any effect at all on the strength of the cipher.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: how to break 1timepads with the same pad used N times
Date: Mon, 24 Jan 2000 11:53:42 -0700
Reply-To: [EMAIL PROTECTED]
Using the following notation:
C1 = first cypher text
C2 = second cypher text
P1 = first plain text
P2 = second plain text
X = OTP key
+ = XOR or other combiner (XOR will be used below)
C1 = P1 + X
C2 = P2 + X
C1 + C2 = P1 + X + P2 + X = P1 + P2 + X + X = P1 + P2
The key has dropped out leaving the XOR of two plaintexts which is not
much harder than the cryptoquotes in newspapers. Of course if not using
XOR, the one uses the inverse of the combining operation.
The above is simplified from the real problems but it covers the main
idea.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Reversibly combining two bytes?
Date: Mon, 24 Jan 2000 11:54:55 -0700
Reply-To: [EMAIL PROTECTED]
Subtraction mod 256
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: Mon, 24 Jan 2000 12:54:29 -0600
David Wagner wrote:
> Hint: Let S be the set of register states where all values are even.
> If you start out in S, you stay in S; if you don't start out in S, you
> never enter S. Thus, the maximum cycle length is at most max(|S|,10^n - |S|),
> and this is strictly less than 10^n - 1.
OK, an easier way to see what you're saying is to write out all possible
n digit numbers and call each one a state. Suppose I can find a
sequence
(I'm not saying I can, let's just suppose!) which goes thru all the n
digit
numbers with at least 1 of them odd, and then goes thru all the n digit
numbers with all of them even. This is not strictly a cycle, but it
could be reset by logic to repeat (suppose the last element is all
zeros).
What combination of polynomials might create such a sequence? (I suppose
a trival case is to do 2 cycles, but I'd rather find one algorithm for
all
inputs which would generate the maximal sequence.)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Laura Feinstein <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.crypt.research
Subject: Weierstrass Normal Form
Date: 24 Jan 2000 18:58:51 -0000
Given the cubic u^3 + v^3 = a, where a is a rational number, how does
one find rational functions, x(u,v) and y(u,v) that will lead to a
Weierstrass equation?
I know the values of the functions:
x(u,v)=12*a/(u + v)
y(u,v)=36*a*(u - v)/(u + v).
I'm looking for an algebraic method for finding these functions.
Laura
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: generating "safe primes"
Date: Mon, 24 Jan 2000 19:00:30 -0000
"Jonathan Katz" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> What are currently used algorithms for generating "safe primes" (numbers
> of the form p = 2q + 1 such that p is prime and q is prime)?
>
> Do they just test for primality of q, then calculate p = 2q + 1, and then
> test primality of p, or something more efficient...?
>
Something more efficient. Randomly generate odd q and calculate p. Try
division by small primes to quickly see if either is composite. If neither
are found to be composite in this way, only then proceed to full
Miller-Rabin primality test for both p and q.
Mike Scott
=====================
Fastest is best.
MIRACL multiprecision C/C++ library for big number cryptography
http://indigo.ie/~mscott
> Jonathan Katz
> [EMAIL PROTECTED]
>
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: generating "safe primes"
Date: Mon, 24 Jan 2000 18:59:50 GMT
In article <Pine.GSO.4.10.10001241225170.20267-
[EMAIL PROTECTED]>,
Jonathan Katz <[EMAIL PROTECTED]> wrote:
> What are currently used algorithms for generating "safe primes"
(numbers
> of the form p = 2q + 1 such that p is prime and q is prime)?
>
> Do they just test for primality of q, then calculate p = 2q + 1, and
then
> test primality of p, or something more efficient...?
More efficient. Select the desired size. Construct a random integer X
of that size. Find a prime q one bit smaller. Find the first odd
integer greater than X congruent to 1 mod q (say Y). Now sieve the
sequence:
Y, Y+2q , Y+4q , ... with small primes.
Then test candidates that survive the sieve for primality.
--
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] (John Savard)
Crossposted-To: sci.math
Subject: Re: Weierstrass Normal Form
Date: Mon, 24 Jan 2000 12:34:04 GMT
Laura Feinstein <[EMAIL PROTECTED]> wrote, in part:
>how does
>one find rational functions, x(u,v) and y(u,v) that will lead to a
>Weierstrass equation?
That clarifies the question. What is a Weierstrass equation?
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: How much random needed for random
Date: Mon, 24 Jan 2000 12:32:24 -0700
Eric Murray wrote:
> BTW the original SSL random-number break (sorry I can't remeber the
> authors names at the moment) was against netscape's SSL implementation
> which used time + process id as the seed to one of the Unix rand()
> functions. Not only is the rand() function not of cryptographic quality,
> but the guys who did the break found that it was easy to find the
> seed values.
Ah. That was Ian Goldberg and sci.crypt's own David Wagner. The paper on the
topic is also must-read if you wish to know why it's evil(tm) to do it this
way. See David Wagner's home page:
http://www.cs.berkeley.edu/~daw/papers/
It's near the bottom ("Randomness and the Netscape Browser").
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Weierstrass Normal Form
Date: Mon, 24 Jan 2000 13:50:32 -0600
John Savard wrote:
>
> On Sun, 23 Jan 2000 17:09:20 -0800, Laura Feinstein
> <[EMAIL PROTECTED]> wrote, in part:
>
> >Given a cubic of the form u^3 +v^3 = a, where a is a rational number, how
> >does one determine new coordinates, x and y given in terms of u and v by
> >rational functions?
>
> >I know the value of these functions:
> >x=12*a/(u + v)
> >y=36*a*(u - v)/(u + v)
>
> >I'm looking for an algebraic method for determining these functions.
>
> Unless the title of your post gives some clue that I'm missing, it's
> hard to see what your question is. Given u^3 + v^3 = a, one knows
> nothing about x and y or their relationship to u and v; thus, the two
> rational functions that you've given can't be determined by algebra.
>
> If you want to find u and v as functions of x and y, that would be a
> straightforwards problem in algebra.
[ solution erased ]
Has Prof. Koblitz thrown you a curve? :-)
Weierstrass has a lot of stuff to his name. Most of the forms I'm
familiar
with are y^2 = x^3 + ... John's solutions are correct for the info
supplied,
but if there are other constraints you'll need to apply those as well.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Weierstrass Normal Form
Date: Mon, 24 Jan 2000 12:55:25 GMT
[EMAIL PROTECTED] (John Savard) wrote, in part:
>On Sun, 23 Jan 2000 17:09:20 -0800, Laura Feinstein
><[EMAIL PROTECTED]> wrote, in part:
>>Given a cubic of the form u^3 +v^3 = a,
Now I know that the following is not what you wanted,
>Knowing u+v and u-v, it's easy enough to find u and v.
>u = (( 12a/x ) + ( y/3x )) / 2
>and
>v = (( 12a/x ) - ( y/3x )) / 2
but substituting it into the original equation, we get:
(12 a/x)^3 + 6 (12 a/x)(( y/3x )^2) = 8a
which, when simplified, gives
8 y^2 = 8a x^3 - 12a.
So, by a Weierstrass equation, you mean one where y^2 can be
represented by a function of x. This at least seems to resemble things
I've turned up in a web search on the phrase.
For the specific case of u^3 + v^3 = a, what you want is a change of
co-ordinates to make the y^3 part cancel out. I have a suspicion that
this may not be simple algebra.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Calculating A^-1 Mod P
Date: 24 Jan 2000 19:23:00 +0100
In article <86h69r$e4u$[EMAIL PROTECTED]>, ink <[EMAIL PROTECTED]> wrote:
> Michael Scott schrieb in Nachricht ...
>>
>>"Kent Briggs" <[EMAIL PROTECTED]> wrote in message
>>news:[EMAIL PROTECTED]...
>>> Michael Scott wrote:
>>>
>>> > An alternative to the Euclidean algorithm.......
>>> > Mike Scott
>>>
>>> I think you meant to say Euler, not Euclid.
>>>
>>
>>No, I meant Euclid. Who lived in Alexandria, Egypt, as did Archimedes and
>>Eratothenes amongst others, as I just found out on an interesting BBC
>>documentary.
>>
>>Euler was German (I think)
>>
>>Mike Scott
>
> He was Swiss. Sorry ;-)
>
> K. In Albon
Did today's Switzerland exist back then? Weren't there just all those
small "German states" over there back in Euler's time?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Twofish question (ciphertext chaining)
Date: 24 Jan 2000 12:02:10 -0800
In article <[EMAIL PROTECTED]>,
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> This process has one full 128-bit encryption for each input byte. I believe
> his question is this: Would it be cryptographically secure to perform one full
> 128-bit encryption for every 16 bytes?
Yes: if I understand you correctly, that mode is called CFB-128.
CFB-128 is easier to understand if we say nothing about shift registers:
C[i] = Encrypt(C[i-1]) XOR P[i].
This is as secure (for message secrecy) as CBC mode, and as fast as can be.
(I think this is in the sci.crypt FAQ, by the way.)
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: LSFR
Date: 24 Jan 2000 12:12:21 -0800
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
> OK, an easier way to see what you're saying is to write out all possible
> n digit numbers and call each one a state. Suppose I can find a
> sequence
> (I'm not saying I can, let's just suppose!) which goes thru all the n
> digit
> numbers with at least 1 of them odd, and then goes thru all the n digit
> numbers with all of them even. This is not strictly a cycle, but it
> could be reset by logic to repeat (suppose the last element is all
> zeros).
>
> What combination of polynomials might create such a sequence? (I suppose
> a trival case is to do 2 cycles, but I'd rather find one algorithm for
> all
> inputs which would generate the maximal sequence.)
I'm sure you can find such an algorithm, but the feedback function
won't be linear, and thus there won't be a "polynomial".
(If I understand the math correctly, characteristic polynomials are
only defined -- and only make sense -- for linear feedback functions.)
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: How much random needed for random
Reply-To: [EMAIL PROTECTED]
Date: Mon, 24 Jan 2000 20:08:45 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: I don't know much about Java but I bet their super fast RNG is just a
: linear congruetial generator. In which case DON'T USE IT FOR ANYTHING
: REMOTELY SECURE.
That one /is/ an LCG - with a modulus of 2^N, and a 48-bit seed ;-(
The Java applet at http://alife.co.uk/nonrandom/ demonstrates its
inadequacies for simple tasks, let alone cryptography.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
We are not punished for our sins, but by them.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Mon, 24 Jan 2000 12:41:33 -0800
"Paul Rubin" <[EMAIL PROTECTED]> wrote ...
: r.e.s. <[EMAIL PROTECTED]> wrote:
: >: Actually it doesn't much matter what order the "card table" is
: >: in, if you have a convenient way to do the arithmetic. So try
: >: it like this:
: >:
: >: 0 40 28 16 4 44 32 20 8 48 36 24
: >: 13 1 41 29 17 5 45 33 21 9 49 37
: >: 26 14 2 42 30 18 6 46 34 22 10 50
: >: 39 27 15 3 43 31 19 7 47 35 23 11
: >:
: >: Now just take the facevalue and suit sums mod 13 and 4 respectively,
: >: independently of each other. If the facevalue sum exceeds 13 just
: >: subtract 13. You don't have to adjust the row sum. This saves you
: >: a step. The Chinese Remainder Theorem in action ;-).
: >
: >I don't think that's correct. Consider DiamondNine+SpadeNine:
: >That's (0,9)+(1,9)=(1,18)=(2,5), not (1,5).
: >Or the long way, (0*13+9)+(1*13+9)=31 =/= 1*13+5.
: >Have I misunderstood your meaning?
:
: (0,9) + (1,9) = (1, 5) is correct.
: The long way: (0, 9) = 48 (found at location 0,9 in the grid)
Ah, there is some notational confusion, but I see what you mean.
(viz., (1,5) as a value 1*13+5=18, and not as a pointer to the
value at location (1,5). My notation uses the latter meaning.)
So if I understand correctly, adding the (row,col) cordinates
separately for the swapped cards, and doing this (mod 4, mod 13),
gives a result (r,c) that directly gives the output value as
13*r+c.
(Excuse me for trying to put your suggestion in my own words.)
--
r.e.s. "Mistr Typo"
[EMAIL PROTECTED]
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Mon, 24 Jan 2000 12:58:52 -0800
"Rex Stewart" <[EMAIL PROTECTED]> wrote ...
: I think you may misunderstand the operation of MirDek. I am guessing -
: I don't know how much time you spent looking at its spec, which changed
: somewhat in the middle of this month.
[...]
I'm sure that's it, because I actually cranked through
MIRDEK quite a few times as it was descibed originally.
He did give fair warning, as I recall, that it was a work
in progress. I'll take a fresh look soon.
: Another note, I intend to try ARC4-m again, because I think it would be
: advantageous to have both card deck ciphers and Cipher Sabre working
: from a common root design.
Note that Paul Rubin recently posted yet another time-saver for
ARC4-52, this one about how best to add the swapped cards to get
the output value.
--
r.e.s. "Mistr Typo"
[EMAIL PROTECTED]
------------------------------
** 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
******************************
