Cryptography-Digest Digest #759, Volume #10 Sat, 18 Dec 99 02:13:02 EST
Contents:
Re: discrete logorithm reduction to factoring (Bodo Moeller)
Re: discrete logorithm reduction to factoring (Bill Unruh)
Re: Euclid Algorithm (lordcow77)
Re: RSA, how to calculate big numbers (Michael J. Fromberger)
Re: Microsoft- PKI/E-comm Director Opening (David A Molnar)
Re: RSA, how to calculate big numbers ("Dann Corbit")
Re: Reducing Key Sizes (Scott Nelson)
Re: Ellison/Schneier article on Risks of PKI (Timothy M. Metzinger)
Re: ARC4 cipher... >> is symmetric stream cipher with UNLIMITED key
([EMAIL PROTECTED])
Re: Euclid Algorithm (Jerry Coffin)
Re: 8192bit Encrypt >> Snake Oil, another one. ([EMAIL PROTECTED])
Re: Microsoft- PKI/E-comm Director Opening (Keith A Monahan)
Re: Euclid Algorithm (Jerry Coffin)
Re: The 20 years periods did apply to 2 of the 3 patents. Why not for
([EMAIL PROTECTED])
Re: Euclid Algorithm ("Dann Corbit")
Re: DES as pseudo rng >> Do you have a key to decrypt "Never eat
([EMAIL PROTECTED])
Re: Euclid Algorithm ("Douglas A. Gwyn")
Re: DES key safety ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bodo Moeller)
Crossposted-To: comp.theory
Subject: Re: discrete logorithm reduction to factoring
Date: 18 Dec 1999 01:38:17 GMT
Bill Unruh <[EMAIL PROTECTED]>:
>> Is it true that discrete log reduces to factoring ?
[Apparently the question is meant the other way around: Can factoring
be reduced to DL; i.e. would an efficient DL algorithm allow us to
factor efficiently.]
> Yes. THis is the whole basis of Shor's quantum result in factoring. What
> Shor really did was to solve the discrete logs, and then show that this
> also solved factoring.
While you keep repeating this again and again, it's not true in any
relevant sense. More specifically, breaking DH modulo some prime p
only allows us to factor p, which isn't such a big deal really :-)
The Shor quantum algorithm for discrete logs works in groups (Z/nZ)*
with n composite or prime. Such general algorithms for DL can indeed
be used for factoring n, but there is no proof whatsoever that
algorithms for discrete logs in (Z/pZ)* with p prime are of any
help for factoring composite integers. (E.g. Pohlig-Hellman gives us
some information about discrete logs in (Z/pZ)*, at least one bit
when the base is a generator, but none for (Z/nZ)* where the
factorization of n is unknown.)
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: discrete logorithm reduction to factoring
Date: 18 Dec 1999 01:38:40 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (DJohn37050)
writes:
>My understanding that is that if you can solve DL, you can also solve IF. This
>means DL may be stronger than IF (or of equal strength). As if you can solve IF
>you may not be able to solve DL.
Went back to the Shor paper.
Given N, find r such that x^r=1 mod N (clearly this would be easily
solved if discrete logs could be easily solved) for random x. If r is
odd, try another x. If r is even, look at x^(r/2). If this is -1, find
another x. If this is not -1, then the gcd (x^(r/2),N) is a factor of N.
(And this is easily calculated).
He argues that the probability of getting a factor for random x is about
1/2. Thus the probablility of finding a factor gets arbitrarily near
one for not very many trials of x.
Thus an efficient discrete logs algorithm implies a probabilistically
efficient factoring algorithm.
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: Euclid Algorithm
Date: Fri, 17 Dec 1999 17:35:58 -0800
TAOCP is not just a crypto book. It is the definitive reference on
practically any algorithmic question. When somebody asks you a question
about algorithms, a pretty safe bet is to say that it's in Knuth's
book, because in all probability it will be.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Michael J. Fromberger <[EMAIL PROTECTED]>
Subject: Re: RSA, how to calculate big numbers
Date: 18 Dec 1999 02:12:44 GMT
In <8sA64.428$Zi.2380@client> "Dann Corbit" <[EMAIL PROTECTED]> writes:
>"Ian Wehrman" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> get on a unix machine, use 'bc'
>>
>> later,
>> ian
>>
>> Bart Peeters wrote:
>> >
>> > I have to calculate:
>> >
>> > (32567023914^367151)%40000399997
>> >
>> > How can I do that?
>Did you actually try it? On my machine, it just pegs the CPU and sits
>there. I have a feeling BC would never complete this task.
>bc 1.04
>Copyright (C) 1991, 1992, 1993, 1994, 1997 Free Software Foundation, Inc.
>This is free software with ABSOLUTELY NO WARRANTY.
>For details type `warranty'.
>x = (32567023914^367151)%40000399997
>It also seems to chow down more and more memory as it runs.
How about:
bc 1.05
Copyright 1991, 1992, 1993, 1994, 1997, 1998 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
define e(a, b, m) {
auto s;
s = 1;
while(b != 0) {
if((b % 2) == 1) {
s = (s * a) % m;
}
b /= 2;
a = (a * a) % m;
}
return (s);
}
e(32567023914, 367151, 40000399997)
726580
This still counts as "using bc," I think.
Cheers,
-M
--
Michael J. Fromberger Software Engineer, Thayer School of Engineering
sting <at> linguist.dartmouth.edu http://www.dartmouth.edu/~sting/
ZUtxdoujdGoD3EZnzFuhh2McmF5zFC0LRAr4izgllQMTIoQkdKFf0rGvpPxBG0VUqwUF5c9A
"Do we find the cost of freedom buried in the ground?
Mother Earth will swallow you; lay your body down..."
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Microsoft- PKI/E-comm Director Opening
Date: 18 Dec 1999 02:46:19 GMT
[EMAIL PROTECTED] wrote:
> I hope I am not breaking group etiquette by
> posting this here, but I think it is highly
> relevant and some of you may be interested...
You know, we have no good reason to believe this is
really from Microsoft. Why not start your PKI effort
by signing this message ? :-)
-David
(no, you have no reason to believe this is from me, either)
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: RSA, how to calculate big numbers
Date: Fri, 17 Dec 1999 19:23:34 -0800
"Michael J. Fromberger" <[EMAIL PROTECTED]> wrote in message
news:83eqis$33r$[EMAIL PROTECTED]...
> In <8sA64.428$Zi.2380@client> "Dann Corbit" <[EMAIL PROTECTED]>
writes:
>
> >"Ian Wehrman" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> get on a unix machine, use 'bc'
> >>
> >> later,
> >> ian
> >>
> >> Bart Peeters wrote:
> >> >
> >> > I have to calculate:
> >> >
> >> > (32567023914^367151)%40000399997
> >> >
> >> > How can I do that?
>
> >Did you actually try it? On my machine, it just pegs the CPU and sits
> >there. I have a feeling BC would never complete this task.
>
> >bc 1.04
> >Copyright (C) 1991, 1992, 1993, 1994, 1997 Free Software Foundation, Inc.
> >This is free software with ABSOLUTELY NO WARRANTY.
> >For details type `warranty'.
>
> >x = (32567023914^367151)%40000399997
>
> >It also seems to chow down more and more memory as it runs.
>
> How about:
>
> bc 1.05
> Copyright 1991, 1992, 1993, 1994, 1997, 1998 Free Software Foundation,
Inc.
> This is free software with ABSOLUTELY NO WARRANTY.
> For details type `warranty'.
> define e(a, b, m) {
> auto s;
>
> s = 1;
> while(b != 0) {
> if((b % 2) == 1) {
> s = (s * a) % m;
> }
> b /= 2;
> a = (a * a) % m;
> }
> return (s);
> }
> e(32567023914, 367151, 40000399997)
> 726580
>
> This still counts as "using bc," I think.
>
> Cheers,
> -M
Once we have the algorithm, the rest is easy. I think the algorithm is what
he (the OP) was asking for. For instance, here is an implementation using
C++ and MIRACL:
D:\MIRACL\SOURCE>type foo.cpp
#include <iostream.h>
#include <flash.h>
Miracl precision = 200;
Big e(Big a, Big b, Big m);
int main(void)
{
unsigned long answer;
cout << e((Big) "32567023914", (Big) 367151, (Big) "40000399997") <<
endl;
return 0;
}
Big
e(Big a, Big b, Big m)
{
Big s;
s = 1;
while (b != 0) {
if ((b % 2) == 1) {
s = (s * a) % m;
}
b /= 2;
a = (a * a) % m;
}
return (s);
}
D:\MIRACL\SOURCE>foo
726580
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Reducing Key Sizes
Reply-To: [EMAIL PROTECTED]
Date: Sat, 18 Dec 1999 04:24:06 GMT
On 18 Dec 1999 [EMAIL PROTECTED] (Keith A Monahan) wrote:
>Scott:
>
>Is your link down?
>
>http://www.helsbreth.org/random/nbitcrc.html
>
Sorry, it was mixed upper and lower case.
http://www.helsbreth.org/random/nbitcrc.html
Should be correct now.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Subject: Re: Ellison/Schneier article on Risks of PKI
Date: 18 Dec 1999 04:36:33 GMT
In article <83ddtk$mne$[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes:
>In the CA->RA model or the CA->CA->RA model, there is one root, which
>if their key is compromised and an attacker issues fake certificates,
>the root will NEVER know, because all they do is issue certificates,
>they can't verify certificates that are floating around in the system.
Which is why so much work goes toward protecting the CA's private key. As the
root of PKI trust, things like physical, personnel, and infosec policy applied
to your CA tell the rest of the world how much trust they can put in your PKI's
work products.
Things like SCIF-level physical security, two (or more) person integrity,
COOPs, full background investigations of CA personnel, and much more need to be
considered when setting up a PKI.
Timothy Metzinger
Private Pilot - ASEL - IA!!!! AOPA Project Pilot Mentor
DOD # 1854 '82 Virago 750 - "Siobhan"
Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: ARC4 cipher... >> is symmetric stream cipher with UNLIMITED key
Date: Sat, 18 Dec 1999 00:09:38 -0500
The RC4 is symmetric stream cipher with unlimited key length >> UNLIMITED
Very common realizations are using key lengths of up to 2048 bits.
The key length of 128 bits in symmetric ciphers is considered to be very
secure,
you can see what increase of the key length to 2048 bits can provide for you.
USA Gov. permitted in the past implementations outside US to be of max 40 bits
key length, which is child play to break for any federal agency.
You can see the / conspiracy / deceive / misinformation / public manipulation /
behind the 40 bit key length.
--
Thanks, Richard
================================================================
Pelle Evensen wrote:
>
> Andrej Madliak ([EMAIL PROTECTED]) wrote:
> : Hi!
> : Has anybody heard of
> : ARC4 stream cipher (w/128-bit key) and/or about its security and
> : attacks against it?
>
> It's "Alleged RC4", something that seemingly behaves identically to
> RSA's RC4 stream cipher.
>
> http://burtleburtle.net/bob/rand/isaac.html
>
> Source and more comments can be found here;
> ftp://ftp.funet.fi/pub/crypt/cryptography/symmetric/rc4/
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Euclid Algorithm
Date: Fri, 17 Dec 1999 22:29:18 -0700
In article <u1H64.4504$HP.37062@news>, [EMAIL PROTECTED] says...
[ ... ]
> Is there any site that give full on-line access to this Knuth's book,
AFAIK, there's not.
> or any other site that explain this topic in detail. I'm having
> trouble on determining the time complexity of Euclid algorithm.
That's not too surprising. Knuth's writeup of it takes up around 18
pages, and in it he quotes none less than Gauss talking about one part
of it, saying "they came out so complicated that no hope appears to be
left." The worst case occurs when the two numbers of which you're
finding the GCD are consecutive Fibbonacci numbers. He gives a worst
case time of approximately [4.8 log10 N - 0.32] were the "[]"
represents rounding up to an integer. I won't try to say more than
that -- there may be somebody who can summarize 18 pages of dense
writing in a single post, but I don't think I can, at least without
spending a lot more time at it than I'm willing to devote to such a
thing right now.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 8192bit Encrypt >> Snake Oil, another one.
Date: Sat, 18 Dec 1999 00:28:02 -0500
Snake Oil, another one.
>From your statements, it's look you do not know what are you talking about.
All claims & statements are not substantiated.
You should consider option to pay someone to use your product as the most
appropriate one, instead asking to pay for your design.
--
Thanks, Richard
========================================================================
Glen Bridgland wrote:
>
> Hi, I new to the group however, I hope to be sharing a lot with the Users
> here over the next few months as I finalise my Project. I am current
> developing an encryption program that will offer 8192bit Encryption along
> with a host of features.
------------------------------
From: [EMAIL PROTECTED] (Keith A Monahan)
Subject: Re: Microsoft- PKI/E-comm Director Opening
Date: 18 Dec 1999 05:37:02 GMT
If this is from Microsoft, then Gates must own deja news, because I can't
think of any other reason for one of the hughest computer companies to use
dejanews to post from.
Keith
David A Molnar ([EMAIL PROTECTED]) wrote:
: [EMAIL PROTECTED] wrote:
: > I hope I am not breaking group etiquette by
: > posting this here, but I think it is highly
: > relevant and some of you may be interested...
: You know, we have no good reason to believe this is
: really from Microsoft. Why not start your PKI effort
: by signing this message ? :-)
: -David
: (no, you have no reason to believe this is from me, either)
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Euclid Algorithm
Date: Fri, 17 Dec 1999 22:38:00 -0700
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> TAOCP is not just a crypto book. It is the definitive reference on
> practically any algorithmic question. When somebody asks you a question
> about algorithms, a pretty safe bet is to say that it's in Knuth's
> book, because in all probability it will be.
Yes and no. It gives excellent, in-depth coverage of most of the
"classical" algorithms, but hasn't really been thoroughly updated
since it was originally written in the mid-1960s. Just for one
example, none of the current methods used for factoring large numbers
gets any mention at all. Of course, it covers the classical methods
on which these are (loosely) based, but deriving the modern methods
from what it covers is certainly FAR from obvious...
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp
Subject: Re: The 20 years periods did apply to 2 of the 3 patents. Why not for
Date: Sat, 18 Dec 1999 00:36:56 -0500
Qb lbh ernyyl xabj jung lbh yvxr gb fnl ?
--
Thanks, Richard
=======================================================
wtshaw wrote:
>
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> > The 3 most known patents in the encryption area are :
> >
> > Name Number Filed Expires
> > ----------------------------------------------------------------
> > Diffie-Hellman 4,200,770 Sept. 6, 1977 Sept. 6, 1997
> > Hellman-Merkle 4,218,582 Oct. 6, 1977 Oct. 6, 1997
> > RSA 4,405,829 Dec. 14, 1977 Sept. 20, 2000
> >
> > The 20 years periods did apply to 2 of the 3 patents.
> > Why it is not applicable to the last one ?
>
> *Contributions*
> --
>
> Pbashgngvf znyrqvpgvf, synzzvf npevohf nqqvpgvf.
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: Euclid Algorithm
Date: Fri, 17 Dec 1999 22:01:19 -0800
"Jerry Coffin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
> > TAOCP is not just a crypto book. It is the definitive reference on
> > practically any algorithmic question. When somebody asks you a question
> > about algorithms, a pretty safe bet is to say that it's in Knuth's
> > book, because in all probability it will be.
>
> Yes and no. It gives excellent, in-depth coverage of most of the
> "classical" algorithms, but hasn't really been thoroughly updated
> since it was originally written in the mid-1960s. Just for one
> example, none of the current methods used for factoring large numbers
> gets any mention at all. Of course, it covers the classical methods
> on which these are (loosely) based, but deriving the modern methods
> from what it covers is certainly FAR from obvious...
It is true that:
Volume 2 "Seminumerical Algorithms", p. 380 'Algorithm A' -- Brute force.
Volume 2 "Seminumerical Algorithms", p. 385 'Algorithm B' -- Rho method.
Volume 2 "Seminumerical Algorithms", p. 387 'Algorithm C' -- Factoring by
addition & subtraction.
Volume 2 "Seminumerical Algorithms", p. 389 'Algorithm D' -- Factoring with
Sieves.
Volume 2 "Seminumerical Algorithms", p. 380 'Algorithm E' -- Factoring via
continued fractions.
Are the only ones spelled out in detail.
But on pages 402-3, he mentions Quadratic Sieve, Elliptic Curve Method,
Number Field Sieve and gives references. I have the (C) 1998 edition which
has been revised.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES as pseudo rng >> Do you have a key to decrypt "Never eat
Date: Sat, 18 Dec 1999 01:05:46 -0500
Do you have a key to decrypt "Never eat anything ..." ?
--
Thanks, Richard
==============================================
Tim Tyler wrote:
>
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> Never eat anything bigger than your head.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Euclid Algorithm
Date: Sat, 18 Dec 1999 06:38:55 GMT
Miryadi wrote:
> I know [Knuth's "Seminumerical Algorithms" ... unfortunately my
> school's library is not well equipped with good crypto refferences. :(
Knuth's "The Art of Computer Programming" books are not "crypto";
they're classics that anyone who has any business implementing
the Euclidean algorithm ought to have in his personal library.
> Is there any site that give full on-line access to this Knuth's book,
No. You can order it directly from the publisher, Addison-Wesley,
or find it at any good technical bookstore.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES key safety
Date: Sat, 18 Dec 1999 06:54:46 GMT
Jerry Coffin wrote:
> In article <83der9$g92$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> > Is DES safe towards the key? I mean if you have the cleartext and
> > the ciphertext could you derrive the key? Theory and practise is
> > two different issues, so actually I'm asking two questions.
> This would be what's called a known-plaintext attack, and no, it's
> not of much use against DES.
Actually that is not known. My last-year's research project was
precisely on general methods for doing such things, and I didn't
determine that it was hopeless. (The project was abandoned due
to lack of funding.) The basic approach was along the lines that
Keith Muller and I worked out many years ago; essentially, you
solve the simultaneous encryption equations; it's a big system,
but easily respresentable within a modern computer's RAM.
Various methods are available for performing efficient reductions.
One question that would be nice to resolve is whether a single
64-bit block of corresponding plain and ciphertext always
determines a *unique* 56-bit DES key. (It's not obvious.)
Modulo that consideration (which can probably be circumvented
by using several blocks), it is obvious that the key is
*theoretically* recoverable, so the issue becomes whether a
practical attack can be found. One hasn't been published yet
(to my knowledge), but that doesn't prove that it is impossible.
(I don't consider brute-force key search practical; it is too
expensive for plain DES and is readily defeated by small changes
to the system, e.g. using 3DES.)
------------------------------
** 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
******************************
