Cryptography-Digest Digest #641, Volume #9 Wed, 2 Jun 99 23:13:03 EDT
Contents:
Re: RSA <> std.encryption (Jerry Coffin)
Re: Question about Cryptography/Encryption... (John Savard)
Re: P3 and OTP ("Douglas A. Gwyn")
Re: Obscure Code (Paul Koning)
Smart Cards ("Steven H. McCown")
Re: Viability of encrypted flash cards? (Phil Hunt)
Re: New Computer & Printer for Dave Scott (fungus)
Re: ECM factoring question (Logic)
Re: RSA theorems--need reminder ("Brian McKeever")
what cipher? ("Particle")
Re: Question about Cryptography/Encryption... ("Brian Hetrick")
Re: what cipher? ("Brian Hetrick")
Re: Obscure Code (SCOTT19U.ZIP_GUY)
Re: Challenge to SCOTT19U.ZIP_GUY (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: RSA <> std.encryption
Date: Wed, 2 Jun 1999 16:09:11 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> > It's certainly possible to give an idea of about the key
> > length needed to make RSA about as difficult to break as DES is, but
> > I'm not sure whether that's what you're asking or not.
>
> Yes, that's what I'm asking :o)
> Can you estimate it mathematically (take me through the calculations)?
Okay. To start with, consider the number of operations involved in
cracking DES. For the moment, I'll assume a brute-force attack is the
best available. DES has a 56 bit key, so there are 2^56 keys. On
average we'll find the right one in about half that many attempts, or
2^55 decryptions.
So, we're looking at the size of key with RSA that results in
approximately 2^55 operations. RSA involves factoring a large number;
at the present time, we'd probably do this using the Number Field
Sieve. In the worst case, the NFS runs in about: exp(O(log^{1/3} n
log^{2/3} log n)). We basically set the result of that to 2^55 and
solve for n. That will give us a tentative result, but ignores (for
the moment) the probability that one operation in the NFS isn't the
same speed as one DES encryption operation. Unfortunately, I don't
really know what the difference in speed is likely to be, though I'd
guess that it would favor DES -- you normally do DES breaking with
dedicated hardware, which does an encryption very quickly.
I should also point out that in both cases (more or less
coincidentally) you start with a number of operations that can pretty
easily be carried out in parallel, and are typically split between a
large number of processors. The result of that is some data that
normally gets crunched more or less serially -- in the case of a DES
breaker, you get some decryptions that _might_ be right, and you use a
more sophisticated test to decide which of them is really right.
These possible decryptions are generated as you go along, so the
sophisticated processing typically happens in parallel with the simple
decryptions.
By contrast, the NFS has to collect all the data from the parallel
operations, and then crunch it serially on a _really_ capable computer
-- typically a Cray. Unless my understanding of NFS is badly
mistaken, this cannot even be started until all the parallel work is
completely finished.
I should mention one other difficulty in doing the comparison: in the
case of DES, you pretty much HAVE to use dedicated hardware to do the
job, and there aren't very many places you can (for example) rent time
on such dedicated hardware. As such, your startup cost is relatively
high, but once you have the equipment, the difficulty isn't that bad.
By contrast, with NFS, you normally end up using normal computers to
do the job. It's fairly easy (in many cases) to do the job with idle
time on machines dedicated to other purposes. If you were going to do
this regularly, buying a Cray (by itself) is more expensive than a
reasonably fast DES breaker, but at a guess it's far easier to rent
some time on a Cray, so if you're only doing this occasionally, it's
probably easier to enter into the game.
Therefore, in the end, there are (at least) two entirely different
possible answers to the question -- are you interested primarily in
the mathematical one in terms of operations and theoretical time, or
are you interested primarily in a practical answer? If you want a
practical answer, you also have to define whether you're talking about
occasional use or whether you're talking about doing this on a regular
basis.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Question about Cryptography/Encryption...
Date: Wed, 02 Jun 1999 22:06:31 GMT
Sundial Services <[EMAIL PROTECTED]> wrote, in part:
>it is set in very large type with wide margins, the very
>opposite of Kahn.
"The Codebreakers", by David Kahn, is set in 10 point Times Roman,
with 2 points leading, IIRC... it is true that it isn't in 'very large
type', but I wouldn't say it's the exact opposite - very small type -
either.
Nor can I charaterize Dr. Kahn's book as unapproachable: it is very
entertaining, and it places things in historical context.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: P3 and OTP
Date: Wed, 02 Jun 1999 22:37:59 GMT
Paul Koning wrote:
> But I don't think anyone has yet published any analysis
> of that generator, so there is no basis on which to believe
> that it is a good generator.
I don't know why there is all this unfounded speculation when
accurate information is readily available on the Internet:
"The [82802] Firmware Hub integrates a Random Number Generator
(RNG) using thermal noise generated from inherently random
quantum mechanical properties of silicon."
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Obscure Code
Date: Wed, 02 Jun 1999 11:03:05 -0400
"Oliver J. Hanau" wrote:
>
> Does anyone now if there is any kind of source on producing obscure
> code, i.e. code that is hard for an attacker to analyze/debug?
> (Assuming the decryption process takes place in an insecure
> environment, and the attacker attempts to find the key and possibly
> also the algorithm.)
Waste of time. Such an exercise makes no sense, and I wouldn't
bother looking for references to such silliness.
paul
------------------------------
From: "Steven H. McCown" <[EMAIL PROTECTED]>
Subject: Smart Cards
Date: Wed, 2 Jun 1999 16:03:40 -0600
Sorry for the cross post, but does anyone know of any sites that deal with
SW development for Schlumberger Smart Cards? Their tech support site is a
bit slow.
Thanks,
Steve
------------------------------
From: [EMAIL PROTECTED] (Phil Hunt)
Crossposted-To: alt.security,talk.politics.crypto
Subject: Re: Viability of encrypted flash cards?
Date: Wed, 02 Jun 99 22:14:22 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>
[EMAIL PROTECTED] "Eric Smith" writes:
> "Cor!" <[EMAIL PROTECTED]>
> writes:
> > If such a system became widely available, then I guess it would be used
> > by criminals more than anyone else (ie. peadophiles, Chinese workers at
> > Los Alamos, etc.).
>
> Why do you say that? Do you think PGP is used by criminals more than anyone
> else? Do you think that non-criminals have no legitimate use for cryptography?
>
> There's almost no statement I find more terrifying than "the innocent have
> nothing to fear."
But it's true! The innocent have nothing to fear. That's why I always
leave my door unlocked (and deposit my keys with the police) and never
write letters, I always use a postcard instead.
Oh, by the way, I'm also happy to post my credit card numbers on Usenet,
together with my address, the expiry date, my mother's maiden name, and
any other information anyone wants.
--
Phil [EMAIL PROTECTED]
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: New Computer & Printer for Dave Scott
Date: Wed, 02 Jun 1999 23:30:14 +0200
Gus James wrote:
>
> You know, he could be the next Ron Rivest. Six hundred dollars is not too
> much to spend on the future of cryptography.
>
Unfortunately, people who've been exposed D. Scotts constant rantings
over the last couple of years won't put too much faith in this possibility.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (Logic)
Subject: Re: ECM factoring question
Date: 2 Jun 1999 19:11:49 -0500
Medical Electronics Lab <[EMAIL PROTECTED]> writes:
>> When doing elliptic curve factorization, we choose an initial point P on the
>> curve. We then calculate the "multiples" of P recursively by performing the
>> group operation on it with a sequence of primes under the chosen bound B.
>> As I understand it, in practice, this sequence is the sorted list of prime
>> powers less than B, where the prime itself replaces each of its powers in
>> the list, e.g. 2,3,2,5,7,2,3,11 and so on.
>So you calculate p1 = 2P, p2 = 3p1, p3 = 2p2, ...
>in that order?
Yes, precisely.
>> In practice, we rarely find a factor in one trial of ECM (unfortunately).
>> Normally we are forced to calculate the multiples of P through the entire
>> sequence. Suppose we instead calculated the multiples of P by each prime
>> until we exceeded B, e.g. 2,2, ... ,2^x<=B, 3,3, ... , 3^y<=B, ...
>> Under the assumption that most trials of ECM yield no factors, could we not
>> gain a slight increase in speed by somehow taking advantage of the fact that
>> we are calculating the same multiple several times (at least for the smaller
>> primes)? Would this make the code simpler as well?
>Do you know the order of P (=k say)? If so, you can compute x^m mod k
>for all the m's you need much faster than computing x^m*P. To make this
>go fast, you can precompute 2^j*P for all j<ceil(log_2(k)), then
>just sum the jth entry for each bit set in x^m mod k.
Unfortunately no, we don't know the order of P. In fact, the goal of ECM
is to find a P whose order is divisible by primes under B (in the first
phase of ECM at least). The reason I asked this is that ECM may be able
to take advantage of the repitition of similar calculations because we are
doing them so many times, as opposed to the (p-1) method.
>This would allow you to trade off space for time, you store lots of
>2^j*P, then just do elliptic curve sums from then on. Do your x^m mod k
>to find out which bits are set using integer math, not EC math.
>Should speed things up quite a bit.
The "exponentiation" (or multiples, depending on what you call the group
operation) is done like this anyway, as I understand. It's a standard
"square and multiply" or "multiply and add" type optimization.
I'm far from understanding the intricacies of ECM, which is why I asked
these questions. I know some people who read this group (Silverman?)
have done some analysis of ECM in the past, so I was hoping someone could
explain why one sequence is faster than another. Nevertheless, thanks
for the thoughts, Dr. Mike. I can always use the food for thought :)
Andy Brown
------------------------------
From: "Brian McKeever" <[EMAIL PROTECTED]>
Subject: Re: RSA theorems--need reminder
Date: Wed, 2 Jun 1999 18:47:40 -0700
It also requires that gcd(c, N) = 1... The proof should be in any basic
Algebra book.
It's simply a consequence of the fact that the order of an element of a
group (here the mulitiplicative group of units of G = Z/NZ) divides the
order of the group (which is phi(N)).
If you are interested in proving this, I believe the proof goes like this:
Take the element c and all its powers: (c, c^2, c^3, ... 1)=H (a group).
Now argue that cosets of H (int G) are either identical or share no
elements, and so |H| (= order of c) divides |G|.
Brian
Bill Unruh wrote in message <7iq1jb$9u$[EMAIL PROTECTED]>...
> was talking with a friend and explaining RSa to him. But for the life
>of me I could not remember how to prove that for all numbers c<N, that
>c^phi(N) mod N =1
>(phi(N) is I think the totient function-- numberof numbers less than N
>relatively prime to N, and equals (usually) (p-1)(q-1) if N=pq, p,q
>prime.)
>In fact I could not remember how to prove that c^(N-1) modN =1 if N is
>prime.
>Any hints please?
>Thanks.
>
>Bill Unruh
>[EMAIL PROTECTED]
------------------------------
From: "Particle" <[EMAIL PROTECTED]>
Subject: what cipher?
Date: Wed, 2 Jun 1999 21:09:19 -0400
I'm looking for a stream cipher, or a block cipher
that works in 8-bit intervals. (actually, I'm looking for
the algorithm, I'm planning on implementing it myself)
It is very important that the ciphertext retain the length
of plain text. It has to be fast, and secure (preferably,
computationally secure). I would use a derivative of
RSA, but that's a bit slow.
Oh, I'm willing to use keys upto 128 bits, which
will be totally randomly generated and secure from
intruders.
it would also be nice to have a feature of not having
to decrypt all the text before a certain point (i.e.: so that
I can seek to the middle of the file, get what I need,
without ever touching the start)
any ideas on a possible algorithm?
please cc reply to my e-mail
thanks.
--
Particle
[EMAIL PROTECTED]
http://www.geocities.com/SiliconValley/Way/7650
Home of the Java Data Structures 2nd Edition.
------------------------------
From: "Brian Hetrick" <[EMAIL PROTECTED]>
Subject: Re: Question about Cryptography/Encryption...
Date: Wed, 2 Jun 1999 21:56:06 -0400
John Savard wrote in message <[EMAIL PROTECTED]>...
>"The Codebreakers", by David Kahn, is set in 10 point Times Roman,
>with 2 points leading, IIRC...
Nitpick alert!
10 point type on 2 point leading would be unreadable. Leading is the
inter-baseline spacing. Perhaps you mean 10 on 12.
For those old-timers who remember typewriters, elite typewriter faces
were 10 on 12; pica were 12 on 12. (Courier fonts typically lie about
their point sizes: they are sized to be set solid, with leading the
same as nominal font size. A Courier 12 is the same size as an
anything else 10.)
Book type smaller than about 8 points is too small to read easily. 9
to 11 points, with leading 120% of font size, is "standard." 10 on 12
is actually a pretty good choice for a book -- or a document, for that
matter. A semicondensed font like Times is fairly reasonable for a
short document, but not really for a book. Palatino (Book Antiqua to
Windows users), or a Garamond, or even (under protest) a Bookman,
would be better. I've never seen _The Codebreakers_, but if it is set
in Times, either the publisher was really trying to control production
costs, or the publisher needs a new book designer.... (IMNSHO)
------------------------------
From: "Brian Hetrick" <[EMAIL PROTECTED]>
Subject: Re: what cipher?
Date: Wed, 2 Jun 1999 21:57:22 -0400
Pick a block cipher, set it up on OFB mode, and voila! a stream
cipher.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Obscure Code
Date: Thu, 03 Jun 1999 02:29:25 GMT
In article <[EMAIL PROTECTED]>, Paul Koning <[EMAIL PROTECTED]> wrote:
>"Oliver J. Hanau" wrote:
>>
>> Does anyone now if there is any kind of source on producing obscure
>> code, i.e. code that is hard for an attacker to analyze/debug?
>> (Assuming the decryption process takes place in an insecure
>> environment, and the attacker attempts to find the key and possibly
>> also the algorithm.)
>
>Waste of time. Such an exercise makes no sense, and I wouldn't
>bother looking for references to such silliness.
>
> paul
If you belive Redburn my software is exactly what yuor looking for.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Thu, 03 Jun 1999 02:27:47 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim
Redburn) wrote:
>On Wed, 02 Jun 1999 02:17:42 GMT, [EMAIL PROTECTED]
>(SCOTT19U.ZIP_GUY) wrote:
>
>>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> (Tim Redburn) wrote:
>
>>>------------------------------------------------------------------
>>> ******* THE CHALLENGE ******
>>>------------------------------------------------------------------
>>>
>>>David, if you think the algorithm is as secure
>>>as you claim, then take the following challenge.....
>>>
>>>Rewrite the source code in a form that is
>>>easily readable by humans. Use descriptive variable
>>>names, avoid macros, etc..
>>
>> I can't use long names. I actaully bent over backwards to
>>use long names. At work the only time I could use long names
>>was to name varibles after people I know. I worked on a quaterion
>>update for a interial navagation system one time and they begged
>>for long names. If you ever see the term "directional analog scaler"
>>I made it up. Some one asked a few years later where I got the math
>>for it. I said I made it up look at the initials. Again i like x y z for
>>variables. I can't speel consistantly enough to write like words.
>> At work I have had to debug look programs one of the first things i do
>>is change the varibles to shorter names so I can look at code and get
>>the stupid words out of the way. It would not be possible to use more
>>descriptive varables. I wish you knew my former bosses they would back
>>up this claim.
>>
>
>Now I understand why you keep talking about former bosses, previous
>jobs, etc.....
>
>I don't know about anyone else but I find :
>
> volume = width * height * depth;
>
>easier to read and understand than:
>
> v = w * h * d;
I like this one but v=x*y*z would be more my style
>
>Here is a small extract from scott19u.c,
>it is from the beginning of the function:
>
> "void doEnce(p19 * a, un32 x)"
>
>---------------------------------------------------------
> /* encrypts a file using 19 bit words */
> un32 iz, izz, i, j, ip, ipp, k, i19, i19s, jj;
un32 is unsigned integer 32 bits in size
> p19 *pp19;
p19 is a structure of 19 bit fields alined to 32 bit boundaries
> po19 *ppo19;
po19 is an offset sturcture of 19 bit fileds alinen to 8 bit boundaries but
when used with the pointer *ppo19 will be set behind the *pp19 pointer
a few bytes so the 19 bit fileds are off set from matching field by 9 bits.
as you see the magor varibles have meaing fill names though short.
> void *v;
v is a void pointer need it to off set ppo19 from pp19 it a weakness in
modern C that old c's did not suffer. C does allow easy movement of
pointers of different types you get an error
>
> if (x < 8) {
> printf(" this method for 8 or more characters only \n");
> exit(1);
> }
>---------------------------------------------------------
>
>An obvious start would be to change 'x' to
>'text_length_in_characters' or something similar, so that it is
>instantly understandable at any point in the code, even places
>where you don't have the printf statement giving you clues.
>Unfortunately that is the only easy one.
>
>Would anyone like to suggest what the other variables
>might be referring to ?
>
>Most people just don't have the spare time to work out just what the
>variables are used for. Many would like to analyse your algorithm,
>but are hampered by having to waste time working out
>what your algorithm actually is.
>
>>>
>>>Take a few days to write an accraute, concise
>>>descrption of the algorithm that can be used by
>>>those who have no programming background to
>>>have a go at analysing it.
>>
>> I am writting in straight C no GNU or DJGPP or endian stuff
>
>That is *not* a plain english description suitable for
>non-programmers. Many cryptographers are mathematicians
>more than they are programmers, and don't
>want the bother of deciphering poorly written* source code.
>
>(*from a human readable point of view.)
>
>>a wrapper program for "wrapped PCBC" so any one can use
>>it I think this will go a long way to anwsering any questions
>>it will be as short a listing as possible.
>>
>
>Why ? Unless thats where you believe the sum total of scott19u.zip's
>security lies ?
No but a lot of it is there and I think it is the wrapping that confuses
people.
>
><snip>
>
>
>>>
>>>As it is, it's a fair bet that you are the only one thats
>>>currently using it.
>>>
>>
>> No I have had letters from people as far away as germany
>>thanking me for this product so some people are using it
>>but I think they are keep a low profile.
>>
>
>How many in total, considering it's available free of charge
>to anyone with internet access. Downloads don't count - I
>downloaded it, but have no intention of using it, not
>while it's so hard to analyse anyway.
>
>
>A 286 PC with MS-DOS and "edit" is all you need. I don't
>understand why you can't rewrite it.
>
>I'm not interested in wrappers - there's to much wrapping on things
>these days, just think about the environment - we just want to get
>at the core of your algorithm and see where the security really lies,
>your reluctance to describe it clearly gives people doubts as to
>it's strength and gives people the impression of security through
>obscurity.
>
>Clear, readable source code, and a clear concise description,
>thats all many on this newsgroup ask. It's not difficult, but
>until you provide them, don't complain when many on this group
>treat your algorithm with great scepticism.
>
>
>You don't seem to be jumping to this fairly easy challenge !!!
>
>Until you do, the doubters will persist.
>
maybe I helped with explaning the above cut of code as you
can see it made perfect since to me.
It is readable!!
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
** 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
******************************
