Cryptography-Digest Digest #166, Volume #12 Wed, 5 Jul 00 18:13:01 EDT
Contents:
Re: Prime Numbers? (Mok-Kong Shen)
Re: Diffie Hellman Primes : Speed Tradeoff Q (Anton Stiglic)
Implementing RSA................ ("Daniele \(Neo\)")
Re: Implementing RSA................ ("Michael Scott")
phun (looz)
Re: Encryption and IBM's 12 teraflop MPC...... (Dan Day)
Re: A thought on OTPs ("Douglas A. Gwyn")
Re: elliptic curves, twofish and re-encryptions ("Douglas A. Gwyn")
Re: Difference between A5/1 and A5/2 (David A. Wagner)
Re: Hash and Entropy (wtshaw)
Re: Help programming (Jeffrey Williams)
Re: Decrypting MD5 (Zulfikar Ramzan)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Prime Numbers?
Date: Wed, 05 Jul 2000 21:26:29 +0200
Big Boy Barry wrote:
> Hello,
>
> As I know, prime numbers are very important to encryption. Is there any
> equation or formula that generates prime numbers? Is it a 'Big Thing' if
> somebody discovered this equation. And why is it important to generate prime
> numbers through an equation not by a prime number generator program... I
> appreciate your help. Thanks!
Look at the thread 'Very large primes' of 28th June in this group.
M. K. Shen
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: Wed, 05 Jul 2000 15:30:58 -0400
Mark Wooding wrote:
> > Lim-Lee primes, primes of the form p = 2*q_1*q_2*...*q_n + 1, where
> > the q_i's are large work fine. You can simply work in one of the
> > subgroups of large prime order.
>
> That only partially answers my question. Do we have a problem if we do
> arithmetic mod p = q R + 1, where q is a large-ish prime, p is large,
> and R is a random composite (therefore possibly having small factors,
> but also likely to have fairly large ones), and work in the subgroup of
> order q?
As far as I know, there is no problem, as long as you work in the
subgroup
of a large prime. You want to be careful against Discreet Log attacks
on
the larger group (mod p), but with at least one prime factor of p-1
being
large enough, I think your o.k. I'd work with Lim-Lee primes just to be
on
the safe side however...
Anton
------------------------------
From: "Daniele \(Neo\)" <[EMAIL PROTECTED]>
Subject: Implementing RSA................
Date: Thu, 29 Jun 2000 15:57:48 +0200
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Hi,
I'm implementing RSA in JavaScript (yea, the same scripting language
used in HTML pages.......).
Both Netscape and Microsoft documentation say that numbers supported
in javascript are included in this range: 1,79E+308 and 1,79E-308 (a
tipical *double* type specification in VB, or Java, or other
programming language.............)
If I work with very small prime number (minor than 8000) my personal
RSA implementation works fine, but if p and q are bigger then 8000,
the RSA algorithm response is wrong.
Obviously I don't use the typical C=M^e mod N (for obvious
mathematical problem.....), but there algorithms (are equivalent, but
the first is quicker than second). I report algorithm in JavaScript
(so similar to C/C++/Java) .|| = "OR", %="mod"
//
// First algorithm
//
function powMod(m,e,n) {
if (n==0||e<0)
return 0
else {
var res=1;
var pow=m;
var e1=e;
var d;
while(e1!=0) {
d=e1%2;
e1=Math.floor(e1/2);
if (d==1) {
res*=pow;
res%=n;
}
pow*=pow;
pow%=n;
}
if(res<0) res+=n;
}
return res;
}
//
// Second algorithm
//
function encodeRSA(m,e,n) {
var bin=e.toString(2); // binary rappresentation of e
var ris=1;
for (var i=0;i<bin.length;i++) {
ris=Math.pow(ris,2);
if (bin.charAt(i)=="1") ris*=m;
ris%=n;
}
return ris;
}
Both these algorithms, as I said, work fine with relative small prime
number. For example,
p=7699
q=7703
powMod(powMod(20,e,n),d,n)=20 // it's ok!
But if
p=329232805929358017357735269927523401527
q=203958913766547634145756211348999961463
and so e=7 and
d=95928522105234920680624433692494227675011019707622401966521732359538
78855859
powMod(powMod(20,e,n),d,n) != 20.
There's no overflow error, but only a wrong
result.....................
Some programmers said to me that problem is in the CPU floating
point........it's right?
Anybody has any idea/advice to resolve this problem??
Thank in advance................
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.5.3 for non-commercial use <http://www.pgp.com>
Comment: PGP key http://asp4free.ravenna2000.it/neowebsite/pubkey.asc
iQA/AwUBOVtHzIyQcjk1tK2MEQKumgCghjdaVOX1bG0oKY9nCuFd2EV0ywwAoJZK
p4aBWRMrx/zwTrtw5qNPzY+5
=Y4+P
=====END PGP SIGNATURE=====
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Implementing RSA................
Date: Wed, 5 Jul 2000 21:07:56 +0100
Alas, while the range: 1,79E+308 and 1,79E-308 would appear to cover numbers
of the size you are interested in, it doesn't. Floating point numbers are
formed from a combination of mantissa and exponent. The former determines
the "number of decimal places" of accuracy in the answer, and the latter
determines the dynamic range. So you can have numbers like .12345 times
10^200, where 12345 is the mantissa and 200 the exponent. But this format
does not allow you to store and manipulate exactly large whole numbers, as
required by RSA.
So for exampe p=329232805929358017357735269927523401527 will be stored as
.32923280592 times 10^39. Most of the least significant digits of the number
are lost. Indeed if you try to print the number out, it will print as
something like:-
3292328059200000000000000000000000
(I have been a little loose in terms of detail to try and make my point)
--
Mike Scott
Fastest is best.
MIRACL multiprecision C/C++ library for big number cryptography
Free implementations of Schoof's Algorithm for Elliptic Curves
http://indigo.ie/~mscott
"Daniele (Neo)" <[EMAIL PROTECTED]> wrote in message
news:8jg12s$c03$[EMAIL PROTECTED]...
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi,
> I'm implementing RSA in JavaScript (yea, the same scripting language
> used in HTML pages.......).
>
> Both Netscape and Microsoft documentation say that numbers supported
> in javascript are included in this range: 1,79E+308 and 1,79E-308 (a
> tipical *double* type specification in VB, or Java, or other
> programming language.............)
>
> If I work with very small prime number (minor than 8000) my personal
> RSA implementation works fine, but if p and q are bigger then 8000,
> the RSA algorithm response is wrong.
>
> Obviously I don't use the typical C=M^e mod N (for obvious
> mathematical problem.....), but there algorithms (are equivalent, but
> the first is quicker than second). I report algorithm in JavaScript
> (so similar to C/C++/Java) .|| = "OR", %="mod"
>
> //
> // First algorithm
> //
> function powMod(m,e,n) {
> if (n==0||e<0)
> return 0
> else {
> var res=1;
> var pow=m;
> var e1=e;
> var d;
> while(e1!=0) {
> d=e1%2;
> e1=Math.floor(e1/2);
> if (d==1) {
> res*=pow;
> res%=n;
> }
> pow*=pow;
> pow%=n;
> }
> if(res<0) res+=n;
> }
> return res;
> }
>
> //
> // Second algorithm
> //
> function encodeRSA(m,e,n) {
> var bin=e.toString(2); // binary rappresentation of e
> var ris=1;
> for (var i=0;i<bin.length;i++) {
> ris=Math.pow(ris,2);
> if (bin.charAt(i)=="1") ris*=m;
> ris%=n;
> }
> return ris;
> }
>
> Both these algorithms, as I said, work fine with relative small prime
> number. For example,
>
> p=7699
> q=7703
>
> powMod(powMod(20,e,n),d,n)=20 // it's ok!
>
> But if
>
> p=329232805929358017357735269927523401527
> q=203958913766547634145756211348999961463
>
> and so e=7 and
> d=95928522105234920680624433692494227675011019707622401966521732359538
> 78855859
>
> powMod(powMod(20,e,n),d,n) != 20.
>
> There's no overflow error, but only a wrong
> result.....................
>
> Some programmers said to me that problem is in the CPU floating
> point........it's right?
>
> Anybody has any idea/advice to resolve this problem??
>
> Thank in advance................
>
>
> -----BEGIN PGP SIGNATURE-----
> Version: PGPfreeware 6.5.3 for non-commercial use <http://www.pgp.com>
> Comment: PGP key http://asp4free.ravenna2000.it/neowebsite/pubkey.asc
>
> iQA/AwUBOVtHzIyQcjk1tK2MEQKumgCghjdaVOX1bG0oKY9nCuFd2EV0ywwAoJZK
> p4aBWRMrx/zwTrtw5qNPzY+5
> =Y4+P
> -----END PGP SIGNATURE-----
>
>
>
------------------------------
Subject: phun
From: looz <[EMAIL PROTECTED]>
Date: Wed, 05 Jul 2000 13:18:45 -0700
http://www.scard.org/gsm/body.html
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: Encryption and IBM's 12 teraflop MPC......
Date: Wed, 05 Jul 2000 20:27:06 GMT
On Fri, 30 Jun 2000 21:19:39 GMT, [EMAIL PROTECTED] wrote:
> Does anyone know how such computing power
>as a 12 teraflop MPC effects current preception of the security of
>various keylengths under various crypto systems?
It doesn't matter much, if at all.
Keep in mind that the difficulty rises so quickly with
increasing keylength that an increase in computing speed
by a factor of a few hundred, or even a few tens of
thousands, doesn't buy you more than another few bits
of key cracking ability, which is trivial.
The best way to keep this in perspective is to realize
that even if every atom in the earth were somehow converted
into a Teraflop computer, and every one of them were
put to the crypto task, it STILL wouldn't be enough to
brute force a moderately large key before the universe
is expected to end.
So no, a computer that's 12,000 times faster than the
fastest new PC on the market doesn't make a really big dent.
Unless, of course, you know a good breakthrough shortcut
algorithm... But a shortcut, if any exists, is just
as likely to be feasible on a 166MhZ Pentium as it is
to require the kind of horsepower a 12 teraflop computer
gives you.
--
"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: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Wed, 5 Jul 2000 19:54:17 GMT
"Tony T. Warnock" wrote:
> "Douglas A. Gwyn" wrote:
> > "Tony T. Warnock" wrote:
> > > A simple version is to note that the characters of the key are independent
> > > and identically uniformly distributed. Thus the probability of getting a
> > > particular cyphertext character is independent of the corresponding
> > > plaintext character and of the position in the message. This is based on
> > > the fact that a convolution of a uniform distribution and any other
> > > distribution on a circle is the uniform distribution.
> > Unfortunately, that argument can also be applied to less secure systems.
> Which less secure system satisfies the independence criterion? Identically
> distributed is easy. Independence is rather difficult.
A trivial example is, take a random key stream but encipher using a
fixed constant operation that makes no effective use of the key stream.
The key is fine but the ciphertext is not. So there is more to it than
merely looking at properties of the key. I.e., your "Thus" is out of
place, since it doesn't introduce a conclusion that follows from what
went before, even though the conclusion happens to be accurate for the
specific system (OTP).
Other, less trivial examples are also possible. Here is just one:
C[i] = P[i] + K[i]^2 mod m, where m is the size of the alphabet.
With this cipher, for a given C[i] only a proper subset of characters
are possible for P[i], which of course is less than perfectly secure.
So it isn't just *using* uniform key at the same rate as PT, but *how*
the key is used.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: elliptic curves, twofish and re-encryptions
Date: Wed, 5 Jul 2000 20:02:14 GMT
Matthew Bennett wrote:
> 2) Re-encryption. It sounds a bit strange, but why is it not standard to
> encrypt a file multiple times? Obviously there are speed considerations,
> but would this not make it almost "impossible" (if there ever was such a
> thing ;) to obtain the original plaintext from multiple-encrypted
> ciphertext?
No, iterating the encryption without using more key doesn't
necessarily make cryptanalysis any harder, and in some cases
it might facilitate it. And if you use additional key, surely
it would be better used along with the other key in a larger
integrated complex encryption algorithm, instead of the total
key being split up and used in two non-interacting processes.
> Surely the attacker would be unable to determine if the data
> had been successfully decrypted back a stage, since there would be nothing
> obvious (like "Dear Sir" it etc.) to show it?
That's not how a cryptanalyst usually works, so it's irrelevant.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Difference between A5/1 and A5/2
Date: 5 Jul 2000 13:57:41 -0700
In article <[EMAIL PROTECTED]>,
Klaus Schmeh <[EMAIL PROTECTED]> wrote:
> The A5 encryption algorithm (used for GSM cell phones) exists in the two
> versions A5/1 and A5/2. A5/2 is said to be less secure.
> Does anybody know what the difference between the two versions is?
A5/1 apparently is (or was) export-restricted.
A5/2 is the exportable version.
A5/2 is thoroughly insecure.
It has something like a 17-bit effective keylength (roughly speaking).
Some attacks on A5/1 are known, but they are not as devastating as
the attacks on A5/2. See the Fast Software Encryption 2000 proceedings.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Hash and Entropy
Date: Wed, 05 Jul 2000 14:44:45 -0600
In article <#y4rnbg5$GA.386@cpmsnbbsa08>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
> Let's see if I can get this right, or at least get my own
> errors pointed out.
> A hash is a function that takes an input of an arbitrary
> length, and creates an output of a fixed length.
The simple requirement of a hash is that there is less information coming
out that going in. This means that some hashes may sometimes be solvable,
including these recreational goodies: running key hash, tridigital hash,
keyphrase hash, whose names do not normally include the implicit term
hash. Or, try this: Slv fr th mnng n ths wrds.
>
> Entropy is a measure of non-determinism inherent in a string
> generated by a method. It has so many different necessary
> interprettations that it becomes difficult to consider, in
> spite of the fact that all the (valid) interpretations are
> in fact equivalent.
The biggest problem is that the word can be taken to be opposite in
meaning, such as "raising" a structure means.... to build it, or tear it
down. Entropy is taken as a measure of order and of disorder in science,
which means that other words are better used, or that improper use is
simply based on a poor understanding of physics.
--
Ralph Nader must not be a politician, he makes sense. Those that
hype confusion about understandable issues are the anarchists.
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: Help programming
Date: Wed, 05 Jul 2000 16:44:32 -0500
I must be missing something here. As I understand it, each plaintext byte is
somehow manipulated based on three key bytes. Each of those key bytes comes
from a different picture file (presumably it could be some other type of file).
I understand that there are a finite number of digitized pictures available and
that that finite number is further limited to the number of such pictures that
the user can access. So you're estimating the keyspace to be 2^40. Now, if
your estimate is the number of pictures available, then shouldn't the keyspace
be 2^120? After all, you use three pictures and you must have all three.
Therefore, it seems to me, that if you have a limited number of pictures
available, you could simply use more pictures.
I don't see keyspace as the real issue here. I think the real issue is whether
the cipher is subject to a non-brute-force attack.
Jeff
Joseph Ashwood wrote:
> > > Why 64bits? That a lot of pictures. The encryption would use all of
> > the bytes of three pictures. And would need the same three pictures to
> > decrypt. A one bit change in one of the pictures and you get mush for
> > an output.
>
> Actually cryptographically speaking 2^64 isn't that big, it actually small
> enough that a public effort has been mounted against one (distributed.net
> RC5 challenge), I was simply stating that 2^64 is the upper limit of the key
> space, more likely the key space is under 2^40.
>
> I wasn't even dealing with the data inside the pictures, from the vantage I
> was taking they merely constitute a key schedule, I was addressing the real
> size of the key (the choice between which pictures to use). The length of
> the key is actually the space from which you choose your keys, Serpent (an
> AES finalist) could be easily broken if you knew the key to be one of 10,
> and Serpent is very good cryptography. It's misleading to consider the size
> of the picture files to be the key for cryptographic purposes simply because
> your choices are much more limited (similar to the US Governments view that
> you can use whatever cryptographic algorithms you want for export, as long
> as there's only x-bits of randomness).
> Joe
------------------------------
Date: Wed, 05 Jul 2000 18:09:56 -0400
From: Zulfikar Ramzan <[EMAIL PROTECTED]>
Subject: Re: Decrypting MD5
Similarly, by using some portion of the hash function payload to store the key,
one can build a keyed family of length preserving functions from a cryptographic
hash function. Then, using these functions as round functions in a Feistel
network yields a block cipher. In particular, if the hash function has a tag size
of n bits, the method described will yield a block cipher on the space of 2n-bit
strings. (For the case of MD5, n=128).
If they keyed family of functions you construct is pseudo-random, then three
iterated Feistel rounds guarantees security against chosen plaintext attacks and
four rounds against chosen plaintext and ciphertext attacks (both adaptive). By
security I mean indistinguishability from a truly random permutation over the same
message space. [These results are due to Luby and Rackoff]
I believe a few ciphers of this form were proposed at FSE98 and FSE99.
Work has been done to make these constructions faster.
One caveat is that the original Luby-Rackoff results are in the asymptotic sense.
Concretely speaking, one can distinguish three and four round ciphers of this form
from random by making on the order of 2^{n/2} queries (where a query represents a
plaintext in the three round case, and a plaintext or ciphertext in the four round
case). These are basically birthday attacks...
Zully.
Steve Rush wrote:
>
> >Eh ? Where did you get that idea from ?
> >
> >A hard to predict key schedule is in no way a guarantee for a good
> >cipher,
>
> But I was referring to cyphers built around secure hash functions. These are
> essentially stream cyphers that use the hash function to generate the
> keystream. If you do it right, you get a good cypher.
>
> --------------------------------------------------------------------------
> --------------
> If it's spam, it's a scam. Don't do business with Net abusers.
--
--Zully
=======
Zulfikar Ramzan (AKA Zully)
Laboratory for Computer Science, MIT
NE43-311, (617) 253-2345
http://theory.lcs.mit.edu/~zulfikar/homepage.html
------------------------------
** 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
******************************
