Cryptography-Digest Digest #134, Volume #13 Fri, 10 Nov 00 12:13:01 EST
Contents:
Re: RSA security (Quisquater)
Re: RSA security (Quisquater)
Re: RSA security (Francois Grieu)
Type 3 Feistel? (Makoto Miyamoto)
Re: RSA security ([EMAIL PROTECTED])
Re: MY BANANA REPUBLIC (SCOTT19U.ZIP_GUY)
Request for code (epiphone)
Re: Q: Computations in a Galois Field (Paul Crowley)
Re: Rijndael and PGP ([EMAIL PROTECTED])
Re: RSA security (Bob Silverman)
Re: RSA security (Francois Grieu)
Re: RSA security ([EMAIL PROTECTED])
Re: hardware RNG's (Alan Rouse)
Re: Rijndael file encryption question. (Russ Housley)
Re: Hardware RNGs (Steve Portly)
Re: RSA security (Bob Silverman)
Re: Request for code (Tom St Denis)
----------------------------------------------------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 11:33:41 +0100
Mok-Kong Shen wrote:
> A bit off-topic: Since you mentioned Cray, I like to
> point out that the currently top supercomputer of the
> world is the Asci White of IBM with 8192 Power-3 processors.
>
> M. K. Shen
Right. Here is the update: http://www.top500.org/list/2000/11/
------------------------------
From: Quisquater <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 12:02:34 +0100
Jim Gillogly wrote:
> They used their own modification of Peter Montgomery's CWI code to run
> on very fat and fast SMP Alphas, including an ES40. They said it's like
> a supercomputer except 1/100 the cost. While they made extensive mods
> to Montgomery's code, they basically used the same NFS and blocked Lanczos
> strategy used for RSA-155.
>
> See http://www.simonsingh.com/cipher.htm for their paper (HTML, PDF, ps
> or dvi).
and see http://www.codebook.org/stage10/stage10.html
for more maths.
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 11:54:03 +0100
[EMAIL PROTECTED] (DJohn37050) wrote:
> I noticed that a cluster of workstations broke RSA 512. Does anyone know
> the RAM used. Some claim that the RAM is the limit that is hit first when
> doing GNFS.
According to <http://codebook.org/codebook_solution.pdf>
- the techniques and most of the source used are the same as for RSA-155,
and overall used "almost twice the computing power compared to what CWI
used when breaking RSA-155", so no theoretical breakthru.
- sieving was done using sievers with "100MB of memory", and produced
75e6 relations
- using a dual processor Alpha DS20 with 4GByte main memory, this was reduced
to 37e6 after the first filtering stage, with 2e6 redundant equations, then
to "8.4e6 equations and variables and a total matrix weight of about 500e6"
- matrix step was done in 13 days on a quad processor Alpha ES40 system
with unspecified memory, and it is estimated it would have taken 37 days
on a system that MAYBE is the above 4GByte DS20. That part used code
somehow optimized for the Aplha.
- the square root step took 11 hours.
Francois Grieu
------------------------------
From: Makoto Miyamoto <[EMAIL PROTECTED]>
Subject: Type 3 Feistel?
Date: Fri, 10 Nov 2000 12:08:08 +0100
Hi,
can anyone point me to a URL, other Internetresource or explain me what
exactly a type 3 Feistel structure is?
When I compare the Feistel networks from MARS and Twofish, I can't tell
why both seem to be type 3?!
What is a type 2 and type 1 Feistel then?
Type 1 = original Feistel like in DES?
Makoto
---
"Ok, Scotty - very funny, now BEAM DOWN MY CLOTHES!"
Makoto Miyamoto
Registered Linux User # 183415
email: [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 11:42:26 GMT
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
> According to <http://codebook.org/codebook_solution.pdf>
> - the techniques and most of the source used are the same as for RSA-
155,
> and overall used "almost twice the computing power compared to what
CWI
> used when breaking RSA-155", so no theoretical breakthru.
> - sieving was done using sievers with "100MB of memory", and produced
> 75e6 relations
I believe that the polynomials chosen for the sieving stage were not
optimal, and this may account for "twice the computing power compared
to what CWI used when breaking RSA-155".
Also they did achieve some parallelisation for the matrix reduction
step, which could be interpreted as a theoretical breakthrough.
Chris
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: talk.politics.crypto
Subject: Re: MY BANANA REPUBLIC
Date: 10 Nov 2000 12:51:45 GMT
[EMAIL PROTECTED] (Runu Knips) wrote in <[EMAIL PROTECTED]>:
>"SCOTT19U.ZIP_GUY" wrote:
>> For those of you not in the US let my explain.
>> The Clinton machine has decided to make GORE president.
>> Many elctions in my country are rigged. Chicago Daly city
>> is famous for having rigged elections. They use to have
>> a saying. In chicago the dead not only vote they vote
>> many times.
>> Apparently they didn't stuff enough ballots in FLorida.
>> They obviously added or exchanged more ballots in the last
>> recount. But You can bet your sweet ass the longer it takes
>> to recount the democrats will perfect the stuffing until
>> Gore wins. Cheating is a way of government in my country.
>> But we have the balls to tell everyone else how to run an
>> election. By the way the democrats desinged the ballot
>> there bitching about.
>> THe next recount if necessary will be desinged to give it
>> to GORE.
>
>If the elections in Florida would have been rigged, the
>result would be CLEAR. Or the people which manipulated
>it are very incompetent losers.
It is rigged it is run by democrats. For Dalys kin is just
not as good as rigging elecltion as it is in Chicago.
But its not over and I feel the crooks will still win.
They know have to readjust the count to wait for the
military ballots to come in so that the proper final
adjustments can me made.
>
>And if the US would have a reasonable election system,
>Gore would be president now anyway.
>
If the US had just laws Clinton and Gore would both
be rotting in prison right now. Instead as Jay Leno says
the confusion is giving the Chinese trouble of where to
send their payola checks. The election system to quite
fair. IF it was on pure majority vote. Rural areas would
have no say in our government at all. Also the effect of
rigged elections would be far greater. At least now the
crooks need to fix the ballots in more than one place,
but that may change if they get there way.
>Just my 0.02$ of logic ...
>
While you 2 cents ain't worth much. My 2 cents thinks
people in Germany may be seeing great parallels as to
historical events in your own country.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: epiphone <[EMAIL PROTECTED]>
Subject: Request for code
Date: Fri, 10 Nov 2000 21:18:10 +0800
Dear All:
I am trying to develop a simple app using Microsoft
Visual C++ 6 using
Crypto++ library writen by Wei Dai. The app is
supposed to perform encryption/decryption on a file/string
using various of today's algorithms.
As I am a novice in encryption technologies and MSVC,
I would like to
ask if there is anyone out there who has written any
similar app using
MSVC 6. I would most appreciate it if anyone can
allow me to look at
his/her code.
Thank you in advance!
Regards,
jon.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Q: Computations in a Galois Field
Date: Fri, 10 Nov 2000 13:21:16 GMT
Mok-Kong Shen wrote:
> It seems, as I mentioned, that there are a number of
> affine transformations that are just as good as the one
> chosen in Rijndael. Could you please say something to
> that? Further I should appreciate to know whether there
> are other transformations in GF(2^8) that are just as
> good as x to 1/x.
If you haven't read Section 7.2 of the Rijndael paper yet I recommend
you do so, it covers this issue.
http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
They mention a paper discussing nonlinear substitutions with good
properties against LC and DC from which they chose x -> 1/x - perhaps
that paper would answer your second question.
Hope this helps,
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Rijndael and PGP
Date: Fri, 10 Nov 2000 14:44:24 GMT
In article <[EMAIL PROTECTED]>,
Richard Heathfield <[EMAIL PROTECTED]> wrote:
> JPeschel wrote:
> >
> > Richard Heathfield [EMAIL PROTECTED] writes:
> >
> > >"SCOTT19U.ZIP_GUY" wrote:
> > >>
> > >That's not what he said. He said "thrown", not "throne". It was a
pun,
> > >which is a kind of joke based on homophones which have distinctly
> > >different spellings and meanings.
> > >
> >
> > A pun? I'd say Ashwood accidentally misspelled throne, as "pretender
> > to the thrown" doesn't make any sense. Doesn't seem to qualify
> > as a humorous non-sequitur, either.
>
> I thought it was funny. I guess I must just have a weird sense of
> humour.
>
> Worse, did I credit Ashwood with a weird sense of humour too?
>
> --
> Richard Heathfield
> "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
> C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
> K&R answers, C books, etc: http://users.powernet.co.uk/eton
>
Extra 1, just for goodluck
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 14:47:48 GMT
In article <8ugmv2$o5f$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Also they did achieve some parallelisation for the matrix reduction
> step, which could be interpreted as a theoretical breakthrough.
How/why do you interpret this as a "theoretical breakthrough"?
Peter Montgomery had already done some experiments on a tightly
coupled SGI R10000 cluster; he reported only getting about 20%
processor efficiency on 16 machines. Running block lanczos is
easy on a *small* number of processors; the problem is that
communication bottlenecks prevent scaling.
--
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: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 16:15:14 +0100
[EMAIL PROTECTED] wrote:
> they did achieve some parallelisation for the matrix reduction step,
> which could be interpreted as a theoretical breakthrough.
Like for RSA-155 the processors used are tightly coupled to a huge
RAM array; they did not distribute the workload and RAM requirement
across workstations, which would have been a breakthrough.
Francois Grieu
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 15:10:50 GMT
In article <8uh1qh$s4$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> In article <8ugmv2$o5f$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>
> > Also they did achieve some parallelisation for the matrix reduction
> > step, which could be interpreted as a theoretical breakthrough.
>
> How/why do you interpret this as a "theoretical breakthrough"?
OK, I withdraw that. But I got the impression that they'd improved on
the current state of the art, even if only by reducing the cost of
hardware required (4 CPU Alpha vs Cray).
> Peter Montgomery had already done some experiments on a tightly
> coupled SGI R10000 cluster; he reported only getting about 20%
> processor efficiency on 16 machines. Running block lanczos is
> easy on a *small* number of processors; the problem is that
> communication bottlenecks prevent scaling.
Has he published these results? I'd heard that he was working on the
problem of parallelizing block lanczos, but I hadn't heard what the
results were.
Chris
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Alan Rouse <[EMAIL PROTECTED]>
Subject: Re: hardware RNG's
Date: Fri, 10 Nov 2000 15:14:05 GMT
David Schwartz wrote:
> Nonesense. Random is not absolute. If I roll a die with a '1'
on one
> side and a '2' on five other sides, the result is random, however it
> will have biases. Your formulation defies common usage as well.
Ok we have established that our differences are semantics. If I am to
communicate further with you on this subject I need a new word that
means to you what "random" means to me. How about arfbixqy? Good
enough? Just replace all my previous usages of "random"
with "arfbixqy" and we'll be fine. ;->
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Russ Housley)
Subject: Re: Rijndael file encryption question.
Date: Fri, 10 Nov 2000 16:10:07 GMT
On 25 Oct 2000 17:23:44 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote:
>[EMAIL PROTECTED] (Mike Rosing) wrote in
><[EMAIL PROTECTED]>:
>
>>ajd wrote:
>>> b) Save the entire final encrypted block before sending to Bob (so we
>>> save 112 bytes of encrypted data instead of 99). The problem here is
>>> that Bob doesn't know how long the original encrypted file was. When
>>> he decrypts he then gets:
>>> oh I do like to be beside the seaside.
>>> Oh I do like to be beside the sea.
>>> where the brass band pl�������������
>>>
>>> We have the whole original method but some extra stuff as well. For
>>> non-text files this could prove to be a problem. Do I use this method
>>> and send the file length to Bob as well or is there another way to get
>>> around the problem?
>>
>>Fill the remaining block with extra known data. The IEEE standard says
>>to fill with 01, 0202, 030303, etc up to the number of bytes you've
>>filled with. that's binary, so you can make it ascii if you like: 1,
>>22, 333, 4444, etc.
>>
>>That way you always send a correct multiple of block data bytes and it's
>>pretty easy to pick off the padding.
>>
>>Patience, persistence, truth,
>>Dr. mike
>>
>
> I would like to see the IEEE standard. I am begining to have a
>gut feelling that they screwed up and asshole manager types may
>have made the actual standard. Anyone know what it really is and
>if there where dumb enough so that some files are ambiguous?
>I wil report anything I learn about this so called standard and
>I will say if its messed up assuming its written so the reading
>itself is not ambiguous.
> I will make one quick point. If it is for use to only fill the
>last encryption block if it is not full it sucks big time.
>
>
>David A. Scott
The technique that you are discussing was originally developed for
Privacy-Enhanced Mail (PEM). See RFC 1423. In PEM, we were using
DES, so the padding was at most eight bytes (an extra block). The
technique extens to any block size less that 255 bytes.
Extract from RFC 1423:
The input to the DES CBC encryption process shall be padded to a
multiple of 8 octets, in the following manner. Let n be the length
in octets of the input. Pad the input by appending 8-(n mod 8)
octets to the end of the message, each having the value 8-(n mod
8),
the number of octets being added. In hexadecimal, the possible
paddings are: 01, 0202, 030303, 04040404, 0505050505,
060606060606,
07070707070707, and 0808080808080808. All input is padded with 1
to
8 octets to produce a multiple of 8 octets in length. The padding
can be removed unambiguously after decryption.
------------------------------
From: Steve Portly <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Fri, 10 Nov 2000 11:21:02 -0500
==============F797E294A3E8B40E82A9FB2C
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
> >> >An assembly language call to int 13 takes a different amount of time than a
>packet arrival.
> >> >The key is to find the minimum time period that will always produces at least
>one bit of
> >> >entropy.
> >> >Since 1995 CPU frequency wander and system jitter have become a source of
>entropy.
> >> >
> >> >http://www.ednmag.com/ednmag/reg/1995/070695/graphs/14dfcfga.htm
> >> >
> >> >With my crude analysis I found that it takes about 40 microseconds to get a bit
>of entropy.
> >>
> >> I for one would like to see the details of that analysis.
> >>
I am sure you would laugh, it was very crude. I timed interrupt thirteen, eight times
summing the
significant digits of each time stamp and dividing by two to create bits. Xored 2
bytes together
to roll up entropy. I tested the distribution by dividing different samples by 2, 8,
256 and
noting how evenly distributed they were. Naturally the results showed a lot of 9's in
the larger
samples, and the distribution didn't swing one way or the other more than about a
hundred any way I
sliced it. Xoring three bytes together didn't flatten the distribution any further
that I could
see, of course my sample size never was larger than a gig. [This should give you a
rough
idea].
>
>
> >> ---
> >> Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
> >> Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
> >
> >It all boils down to how long it takes you to roll up enough entropy to satisfy
>your needs.
>
> First of all, an exponential wait will kill you. To collect the next
> bit of the difference between oscillator frequencies, you must wait
> twice as long as you did for the last bit. Just how long do you think
> this can possibly be a reasonable source?
>
The entropy is roughly the same for each 20 microsecond interrupt timing.
I agree that Xoring bytes together is going to give you diminishing returns.
The point that needs to be proven or not is whether the initial quality of raw data
has enough
entropy to be usable. My tests were too small to prove this obviously. Your site has
some very
good links, and I think following the back button link on the electronic daily news
magazine would
give some additional insight.
==============F797E294A3E8B40E82A9FB2C
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
<br>
<blockquote TYPE=CITE>>> >An assembly language call to int 13 takes a different
amount of time than a packet arrival.
<br>>> >The key is to find the minimum time period that will always produces
at least one bit of
<br>>> >entropy.
<br>>> >Since 1995 CPU frequency wander and system jitter have become a
source of entropy.
<br>>> >
<br>>> ><a
href="http://www.ednmag.com/ednmag/reg/1995/070695/graphs/14dfcfga.htm">http://www.ednmag.com/ednmag/reg/1995/070695/graphs/14dfcfga.htm</a>
<br>>> >
<br>>> >With my crude analysis I found that it takes about 40 microseconds
to get a bit of entropy.
<br>>>
<br>>> I for one would like to see the details of that analysis.
<br>>></blockquote>
I am sure you would laugh, it was very crude. I timed interrupt thirteen,
eight times summing the significant digits of each time stamp and dividing
by two to create bits. Xored 2 bytes together to roll up entropy.
I tested the distribution by dividing different samples by 2, 8, 256 and
noting how evenly distributed they were. Naturally the results showed
a lot of 9's in the larger samples, and the distribution didn't swing one
way or the other more than about a hundred any way I sliced it. Xoring
three bytes together didn't flatten the distribution any further that I
could see, of course my sample size never was larger than a gig.
[This should give you a rough idea].
<blockquote TYPE=CITE>
<p>>> ---
<br>>> Terry Ritter [EMAIL PROTECTED] <a
href="http://www.io.com/~ritter/">http://www.io.com/~ritter/</a>
<br>>> Crypto Glossary <a
href="http://www.io.com/~ritter/GLOSSARY.HTM">http://www.io.com/~ritter/GLOSSARY.HTM</a>
<br>>
<br>>It all boils down to how long it takes you to roll up enough entropy
to satisfy your needs.
<p>First of all, an exponential wait will kill you. To collect the
next
<br>bit of the difference between oscillator frequencies, you must wait
<br>twice as long as you did for the last bit. Just how long do you
think
<br>this can possibly be a reasonable source?
<br> </blockquote>
<tt>T</tt>he entropy is roughly the same for each 20 microsecond
interrupt timing.
<br>I agree that Xoring bytes together is going to give you diminishing
returns.
<br>The point that needs to be proven or not is whether the initial quality
of raw data has enough entropy to be usable. My tests were too small
to prove this obviously. Your site has some very good links, and
I think following the back button link on the electronic daily news
magazine would give some additional insight. </html>
==============F797E294A3E8B40E82A9FB2C==
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA security
Date: Fri, 10 Nov 2000 16:29:01 GMT
In article <8uh35j$21p$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
<snip>
> > Peter Montgomery had already done some experiments on a tightly
> > coupled SGI R10000 cluster; he reported only getting about 20%
> > processor efficiency on 16 machines. Running block lanczos is
> > easy on a *small* number of processors; the problem is that
> > communication bottlenecks prevent scaling.
> Has he published these results? I'd heard that he was working on the
> problem of parallelizing block lanczos, but I hadn't heard what the
> results were.
He presented them at the 2000 RSA COnference.
--
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: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Request for code
Date: Fri, 10 Nov 2000 16:37:12 GMT
In article <[EMAIL PROTECTED]>,
epiphone <[EMAIL PROTECTED]> wrote:
> Dear All:
>
> I am trying to develop a simple app using Microsoft
> Visual C++ 6 using
> Crypto++ library writen by Wei Dai. The app is
> supposed to perform encryption/decryption on a file/string
> using various of today's algorithms.
>
> As I am a novice in encryption technologies and
MSVC,
> I would like to
> ask if there is anyone out there who has written
any
> similar app using
> MSVC 6. I would most appreciate it if anyone can
> allow me to look at
> his/her code.
>
> Thank you in advance!
Ask this in a MSVC newsgroup not sci.crypt.
Also I doubt anyone is about todo your homework.
Also why not start learning C and not C++ first, and avoid machine
specific C extensions... learn basic console C stuff first!!!
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
