Cryptography-Digest Digest #728, Volume #11 Sun, 7 May 00 23:13:00 EDT
Contents:
Re: Is this random? (David Hopwood)
Re: Questions about imaginary quadratic orders (David Hopwood)
Re: Newbie question about primes (Remco Gerlich)
distributed RSA? (Tom St Denis)
Re: RC5 question (Scott Contini)
Re: GPS encryption turned off (Matthew T. Russotto)
Autokey (HerbertYardley)
Re: Factoring RSA (Scott Contini)
Re: SBOX program using ideas from CA and ST (CAST design) (Terry Ritter)
Re: Autokey (Jim Gillogly)
----------------------------------------------------------------------------
Date: Sun, 07 May 2000 05:01:18 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Is this random?
=====BEGIN PGP SIGNED MESSAGE=====
Benjamin Goldberg wrote:
> I've come across a number generator written in java which claims to be
> "truly random" number generator (not a PRNG)... Could someone tell me
> how accurate (or inaccurate) this claim is?
>
> public class ThreadYieldGenerator
> extends java.util.Random
> implements Runnable {
>
> public static final java.util.Random TYG =
> new ThreadYieldGenerator();
>
> private Thread generator;
> private long time = 1000;
Even if you accept the basic idea of counting the number of yields in
a specified time, 1000 ms is not long enough.
> private int count;
>
> private ThreadYieldGenerator() {
> generator = new Thread(this,"TYG-generator");
> generator.setDaemon(true);
> generator.start();
> }
>
> public synchronized byte getByte() {
> try {
> generator.join();
> } catch(InterruptedException ie) {
> generator.stop();
> }
Yuch. This is not at all portable between different Java implementations.
Also, Thread.stop() is deprecated, and may be removed from the Java spec
in future for security reasons.
> int count = this.count;
> generator = new Thread(this,"TYG-generator");
> generator.setDaemon(true);
> generator.start();
I don't like the way the generator thread is joined and restarted for
each byte. Not only is it unnecessarily inefficient, the way this is
done makes the quality of the randomness very dependent on the pattern
of timing of calls to getByte.
> return (byte)count;
> }
>
> public void run() {
> if( Thread.currentThread() != generator ) {
> try {
> Thread.sleep(time);
> } catch(InterruptedException ie) {
> }
> return;
> }
Using the same class for two different thread types is a really
inelegant kludge.
> do {
> count = 0;
> Thread sleeper = new Thread(this,"TYG-sleeper");
> sleeper.setDaemon(true);
> sleeper.start();
> while( sleeper.isAlive() ) {
> Thread.yield();
> ++count;
> }
This is not a good way to do a spin counter. The resolution of
the count will be severely limited because of the execution time of
Thread.yield().
> time = ( time * 55000 / count ) | 1;
> } while( count < 33000 );
> }
>
> private long bitsValue = 0;
> private int bitsCount = 0;
> public int getInt(int nbits) {
> if( nbits > 32 || nbits < 0 )
> return 0;
Rather poor handling of unexpected arguments.
All in all, I'm not impressed. The default seeding method for
java.security.SecureRandom in the standard API does something similar,
but does a much better job of it.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBORTqXTkCAxeYt5gVAQEWqAgAj9WpX75aFsdc/5M6wFqkDm+gy3H+C9Vm
ejCfdvQH/3GqtsKRHPG3fJUnuVKN3L6M9sK6cnbSuPbEA6W6hMXlnQBPDw/Pv4lz
ZHJFBLToWIWwHfszs2+JcY6Ix/zLcOcX5PPVR7Yeo1xZpzmRA65T5IeKXCGV1seu
icNd09fnQHlZG0nhQATOiG6q1GMfn0F2jKBIQvVMWReGxVrknSG73nzaxSJf9g5/
b5spndOhogOmblCj+ETUHdZk4dg2tFaH4LGCE6BKhk9ndBsBYne8GOcydCydyHci
9wwxvYun6sfTyROmOfPgQBj8FwTaISNwLapfcIk1z3QMPng0udubPQ==
=U/SG
=====END PGP SIGNATURE=====
------------------------------
Date: Mon, 08 May 2000 00:37:11 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Re: Questions about imaginary quadratic orders
=====BEGIN PGP SIGNED MESSAGE=====
Jan-Christoph Puchta wrote:
> David Hopwood wrote:
>
> > Let Delta be a negative integer such that abs(Delta) is prime, and
> > Delta is congruent to 1 (mod 4),
> > q be a prime integer,
> > Delta_q = Delta.q^2,
> > Cl(Delta) be the class group of the maximal imaginary quadratic order
> > with discriminant Delta,
> > Cl(Delta_q) be the class group of the non-maximal imaginary quadratic
> > order with discriminant Delta_q.
>
[...]
> > 2. What is the expected size or range of |Cl(Delta)| [i.e. h(Delta)],
> > and does its factorisation "look like" the factorisation of a random
> > integer of about the same size?
>
> AFAIK the best effective bounds are
> C_1 (log log Delta)^(1/2) < h(Delta) < C_2 Delta^(1/2) log Delta.
> However, if GRH holds, we have
> C_1 Delta^(1/2) (log log Delta)^(-1) < h(Delta) < C_2 Delta^(1/2) (log
> log Delta),
> and this is sharp. Further, you can replace GRH with some
> finite statement like "L(s, \chi) has no zero in the domain Re s> 6/7,
> Im s < log^3 Delta", then using density estimates one gets that the
> estimate for h(Delta) holds for almost all Delta unconditionally (but
> with weaker constants).
OK, so far so good.
> The factors of h(Delta) are not completely random, the Gauss' theory of
> genus describes its 2-part,
I'm afraid you've lost me here, but I'll look up Gauss' theory of genus.
I'm not sure it's really important, provided Delta can be chosen such
that h(Delta) can be factored.
It would be nice to be able to ensure that h(Delta) has a prime factor
of about 200 bits, so that the cryptosystem can work in a subgroup of
that size, for efficiency. The ideal case would be h(Delta) = c k p,
where k and p are prime, k is 200 bits, and c is small (say < 20 bits).
> and you can construct Delta such that
> h(Delta) is divisible by some prescribed prime. E.G. if the equation
> x^2+Delta = y^k is solvable, in most cases (there are some trivial
> solutions) we have k|h(Delta).
Presumably this can't be used to construct Delta s.t. k | h(Delta) for
large k, though, because y^k would be too big? Or is there some way to
do this without explicitly calculating x^2 and y^k?
> > 5. In Cl(D) and in Z*_n (the group of units modulo a composite integer
> > n), taking discrete logarithms requires factoring a parameter that
> > describes the group (D or n), then calculating discrete logarithms
> > in a smaller group or groups dependent on the factorisation.
> >
> > Are there any other finite groups that share this property?
>
> What about abstract cyclic groups? Assume you have an algorithm to
> compute the product of two elements and to check equality of elements,
> and that a generator a of G is given. Factor |G|. Choose some k| |G|
> with (k, |G|)=1.
Surely if k | |G| then gcd(k, |G|) = k?
> Then we have G = U x V for subgroups U, V with |U|=k,
> |V|=|G|/k. We can choose U=<a^(|G|/k)>, V=<a^k>. Assume that we can
> solve discrete logarithms in U and V. Let x in G be given, and we want
> to compute some l such that a^l=x in G. Compute x^(|G|/k). This is in U,
> solving discrete logarithms in U gives some n such that a^(n |G|/k) =
> x^(|G|/k), in V we find some n' such that a^(n' k) = x^k. Find integers
> u, v, such that u(|G|/k) + v k = 1, and we obtain a^(u n |G|/k + v n'
> k) = x, hence we found our logarithm.
Yes, I know that given the factorisation of |G|, finding discrete logs in
G is as easy as finding discrete logs in subgroups of size equal to the
factors. However, I also need the converse: that finding discrete logs
in G is not feasible without the factorisation.
This isn't true for an arbitrary large enough cyclic group (counterexample:
Z+_n, with g^x = g * x mod n, where the "discrete log" of x to base g is
just g^-1 * x mod n, which can be efficiently calculated without knowing
the factors of n).
The problem I've had so far is that groups that have been studied for use
in discrete-log-based cryptosystems are chosen because the DLP is as hard
as possible. I'm looking for some set of groups defined by G(n) in which
the DLP is easy, but only when n is a prime (of up to 300 or 400 bits),
i.e. not so easy that it can be calculated for composite n without knowing
the factors.
In any case, thanks, you've been extremely helpful.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBORX+BDkCAxeYt5gVAQGTmQf8D4W6Q3NJl2UfiMY0vEBoDJMos2EOc10F
mdr3YDqgYEoZk9ruSpDLKlTfTWzwhEtLHvxcpaxrXUcRcDQj/IyXtFfA3GJiN5hs
nu9dmzQwP3RUyX6e4erWxehO+tR0/UrvP2ScCQasPDFSwVXnx33TZEW2xiVN4RTE
vEINfRAHIfdgvRRNj6/IWoAdsktFIk/qHcPqZzmbFJux+vCitIOXmCdZ3rYY4Gbx
3mhcbBsZ9MStmlsUR2H4pfUq6Aj8HSSle0hJUUlfOmUyko2ftWu8vg1sZcrk4GKe
rem9mx5BV00B3XWB76gshCEHACBTVsM3mqAUUVMXN+7XjMIM8IyRLg==
=5LTn
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Remco Gerlich)
Subject: Re: Newbie question about primes
Date: 8 May 2000 00:19:38 GMT
Reply-To: [EMAIL PROTECTED]
JoeC wrote in sci.crypt:
> As I understand it, one of the key factors(pardon the pun) in the security
> of PGP and similar is the time taken to factor a large prime number.
Prime numbers have two factors, 1 and themselves.
> Does it not take an equally large amount of time to create a prime, which I
> would need were I to create a private/public key pair? Obviously it can't,
> or the thing wouldnt work.
> Could someone point me at a good source (or is there a quick explanation)
> for the obvious time difference between creating a prime compared to
> factoring one, since I thought in order to determine if a number was prime,
> you had to factor it?
There are tests to see if a number is prime. Most of them are probabilistic,
I.e., they are usually right, not always. Run a lot of them, and you can be
sure that a number is prime, beyond any border of doubt you like to set. But
you can't factor it in that time.
So you find two prime numbers in this way (try random huge numbers until you
find two) and multiply them. Good luck with factoring.
[posted because atm I feel this is maybe a bit shorter/clearer than some
other replies - though I can't give an URL to the probabilistic algorithm I
described atm]
--
Remco Gerlich, [EMAIL PROTECTED]
This is no way to be
Man ought to be free -- Ted Bundy
That man should be me
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: distributed RSA?
Date: Mon, 08 May 2000 00:55:28 GMT
Is there any pratical use for distributed RSA? I can see it for large
computer networks so you save space in a directory by not storing the
modulus, and do a key escrow...
Basically I see it as
The server makes up 'p' and 'q', and keeps N=pq public. Whenever you
want your own key you start a DH secured link with the server where you
put your userid and request a key... i.e
1. Parties share g^x^y via DH and hash it (with say MD5) to make a
secret shared key K
2. Client encrypts his name/userid using a symmetric cipher and K
3. Server encrypts the clients private/public exponents with symmetric
cipher and K
4. Server adds the public key to the directory and possibly the private
key too.
Among the users of the server the keys are never compromised, but I can
see several main flaws...
1. Compromisation of the server is a Bad Thing (tm)
2. Factorization of N is a Bad Thing (tm)
So wouldn't a public shared ElGamal system be better? Where the modulus
(around 768 bits) and generator are public. The clients public key
would be the same size, just the ciphertext would be bigger...
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] (Scott Contini)
Subject: Re: RC5 question
Date: 8 May 2000 01:51:41 GMT
In article <8f4m83$6s2$[EMAIL PROTECTED]>, Pred. <[EMAIL PROTECTED]> wrote:
>Hi.
>
>I read a paper on RC5 and it states that the key expansion process has
>a certain degree of onewayness.
>
>What does this is mean? Is it or is it not possible to derive the key
>from the S-table by other means than brute force?
If it is one-way, then it should not be possible.
>
>The reason I ask is that the paper describes attacks in which the goal
>is to find the S-table. But the attack is not always good if it's very
>difficult to get from S to the secret key. This because it's not
>possible - I think - to figure out the key selection process if you
>only have the S-table.
>
> - Pred
>
Why do you need the original key if you have the S-table? The S-table
is all you need to encipher and decipher anything you want.
Scott
------------------------------
Crossposted-To: sci.geo.satellite-nav
Subject: Re: GPS encryption turned off
From: [EMAIL PROTECTED] (Matthew T. Russotto)
Date: Mon, 08 May 2000 01:49:29 GMT
In article <8f165q$kdv$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
}
}The DoD performs an extensive security review of PPS receivers. PLGRs
}have passed the review and are considered Unclassified. Unlcassified
}DOES NOT mean available to the general public. PLGRs are Unclassified,
}but are not available to the general public
IIRC, the US Forestry Service had some of them -- the procedure for
signing one out (sorry, employees only) used to be somewhere on the net.
--
Matthew T. Russotto [EMAIL PROTECTED]
"Extremism in defense of liberty is no vice, and moderation in pursuit
of justice is no virtue."
------------------------------
From: [EMAIL PROTECTED] (HerbertYardley)
Subject: Autokey
Date: 08 May 2000 02:16:58 GMT
What is the technique for breaking an autokeyed message?
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Factoring RSA
Date: 8 May 2000 02:20:20 GMT
In article <8f4akk$qrj$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>I would like to know, given a factoring time ot Ft for an n digit RSA,
>how to claculate the asymptotic time increment Ft' for n' (n'>n) for
>the following algorithms:
>
>CFRAC
>GNFS
>SNFS
>
>Thanks
>
>
Just use the asymptotic running time formulas, except ignoring
the "o(1)".
running times (omitting "o(1)"):
SNFS:
T(n) := e ^ [ c * (log n)^(1/3) * (log log n)^(2/3) ]
where c := (32/9)^(1/3)
GNFS:
T(n) := e ^ [ c * (log n)^(1/3) * (log log n)^(2/3) ]
where c := (64/9)^(1/3)
CFRAC:
T(n) := e ^ [ ( 2 * (log n) * (log log n) )^(1/2) ]
all logs are natural logarithms.
For example, n' is approx T(n')/T(n) times harder to factor
than n .
Scott
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: SBOX program using ideas from CA and ST (CAST design)
Date: Mon, 08 May 2000 02:36:53 GMT
On Sun, 07 May 2000 20:59:18 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> On Sun, 07 May 2000 15:05:56 GMT, in <[EMAIL PROTECTED]>,
>> in sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote:
>>
>> >Tim Tyler wrote:
>> >>
>> >> WT(F, alpha, beta)
>> >> {
>> >> sum = 0
>> >> for x = 0 to w
>> >> sum = sum + (-1)^((alpha . x) * (beta . F[x]))
>> >> return sum
>> >> }''
>> >>
>> >> This looks like no FWT I'm familiar with.
>> >
>> >It's the WT transform from Matsui's linear cryptanalysis.
>> >
>> >I would gladly switch to the FWT (I have seen it mentioned elsewhere) if
>> >I could get some pseudo-code (Sorry Terry I don't have the time to
>> >figure out your javascript program...)
>>
>> Let's see: You don't have time to analyze working and finished code,
>> yet think that others should have time to analyze your non-working
>> code which you will soon change.
>>
>> What is wrong with this picture?
>>
>> Here is the JavaScript for just the FWT taken directly from
>>
>> http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM
>>
>> function BitARFWT() {
>> // Hadamard Walsh from sequential data, in-place
>> // transform bit array
>> var block=pair=el1=el2=a=b=0;
>> var stradwid = 1; // distance between pair of elements
>> var blocks = bitARlast; // ASSUMED to be 2**n - 1
>>
>> while (stradwid != 0) {
>> el1 = 0;
>> blocks >>>= 1;
>> for (block=0; block <= blocks; block++) {
>> el2 = el1 + stradwid;
>> for (pair=0; pair < stradwid; pair++) {
>> a = bitAR[ el1 ];
>> b = bitAR[ el2 ];
>> bitAR[ el1 ] = a + b;
>> bitAR[ el2 ] = a - b;
>> el1++; el2++;
>> }
>> el1 = el2;
>> }
>> stradwid = (stradwid + stradwid) & bitARlast;
>> }
>> }
>>
>> That looks fairly C-like to me, except ">>>" which is an unsigned
>> 32-bit right shift of n bits (the parameter). (In JavaScript ">>" is
>> a signed shift.)
>
>Ok can you explain all the variables please?
>
>I assume bitAR is the table?
Yes, an array of 32-bit values.
>block is the number of bits? ...
Nope; block is just an internal counter.
Other than the array of values, the only other input parameter needed
is bitARlast, which is the index of the last element in the array.
The values in the array are simply transformed.
You might compare the JavaScript code to the text and Pascal code in
http://www.io.com/~ritter/ARTS/MEASNONL.HTM
e.g.,
"A Fast Walsh Transform Routine
The Fast Walsh Transform by hand is automated in the Borland Pascal
listing of Figure 10.
A Fast Walsh Transform (FWT) in Pascal Fig. 10
TYPE
Lwd = LongInt;
LintArray = ARRAY[ 0..16380 ] of LONGINT;
PROCEDURE LintHadFmSeqWalsh( VAR DatLintAr; lastel: Lwd );
{ Hadamard Walsh from sequential data, in-place }
VAR
Dat: LintArray ABSOLUTE DatLintAr;
a, b: LONGINT;
stradwid, { distance between pair of elements }
blockstart, block, pair, el1, el2: Lwd;
BEGIN
stradwid := 1;
blockstart := lastel;
REPEAT
el1 := 0;
blockstart := blockstart DIV 2;
FOR block := blockstart DOWNTO 0 DO
BEGIN
el2 := el1 + stradwid;
FOR pair := 0 TO PRED(stradwid) DO
BEGIN
a := Dat[ el1 ];
b := Dat[ el2 ];
Dat[ el1 ] := a + b;
Dat[ el2 ] := a - b;
Inc( el1 ); Inc( el2 );
END;
el1 := el2;
END;
stradwid := (stradwid + stradwid) AND lastel;
UNTIL (stradwid = 0);
END; {LintHadFmSeqWalsh}
LintHadFmSeqWalsh takes an array of 32-bit integers, and changes the
array data into the Walsh-Hadamard transform of that data. For
nonlinearity measures, the input data are {0,1} or {1,-1}; the
results are potentially bipolar in either case. (The "lastel"
parameter is the last index in the data array which starts at
index 0; it is thus always 2**n - 1 for some n. The ABSOLUTE
attribute forces Borland Pascal to treat the parameter as a LongInt
array of arbitrary size.)"
I note that there is an explanation of how to do the transform by hand
prior to that text and code.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Autokey
Date: Mon, 08 May 2000 03:05:38 +0000
HerbertYardley wrote:
>
> What is the technique for breaking an autokeyed message?
What kind? Plaintext autokey? Ciphertext autokey? Something else?
As a general rule, known plaintext (or probable words) helps, for
use with crib-dragging. Try to identify the length of the key.
See the section in Helen F. Gaines' "Elementary Cryptanalysis"
titled "Auto-encipherment" for more detailed instructions. Military
Cryptanalysis Part III (Friedman) has some information on it,
as does Military Cryptanalytics Part III (Callimahos), which
unfortunately isn't yet republished.
--
Jim Gillogly
Mersday, 18 Thrimidge S.R. 2000, 02:59
12.19.7.3.8, 7 Lamat 11 Uo, Fifth Lord of Night
------------------------------
** 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
******************************
