Cryptography-Digest Digest #972, Volume #10 Tue, 25 Jan 00 14:13:01 EST
Contents:
Re: Why did SkipJack fail? (John Savard)
PGP and Sendmail, remailer help please ([EMAIL PROTECTED])
Re: "Trusted" CA - Oxymoron? (Jimmy Doughan)
Re: What about the Satanic Seven??? (Sander Vesik)
Re: Reversibly combining two bytes? (Tim Tyler)
Re: What about the Satanic Seven??? (Sander Vesik)
Re: simplistic oneway hash (Michael Wojcik)
finding gcd in the large multiplicative group... (Taekyoung7)
Re: Java's RSA implimentation (David Eppstein)
Court cases on DVD hacking is a problem for all of us (Troed)
Re: Reversibly combining two bytes? (Michael Wojcik)
Re: 1on1lite (Was: Re: Echelon monitors this group) (wtshaw)
Re: "Trusted" CA - Oxymoron? (Timothy M. Metzinger)
Re: Does RSA use real prime ? (Greg)
Re: LSFR (Mike Rosing)
Re: Does RSA use real prime ? (Greg)
Re: Modem Crypto (Military Grade) ([EMAIL PROTECTED])
Re: Does RSA use real prime ? (Greg)
Re: Transposition over ASCII-coded text (Mike Rosing)
Re: RNG for OTPs during WWII (Jim Reeds)
Re: finding gcd in the large multiplicative group... (Mike Rosing)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Why did SkipJack fail?
Date: Tue, 25 Jan 2000 09:04:40 GMT
[EMAIL PROTECTED] (Paul Rubin) wrote, in part:
>You're confusing Skipjack with Clipper.
It might be more accurate to say that the original poster did so, and
the one responding did not trouble to correct or quibble.
But if one does want to explore the question of why SKIPJACK itself
failed to catch on, there are answers to that one too.
1) When it was declassified, the AES candidates were public, which had
longer keys and a larger block size; hence, more secure alternatives
were available.
2) SKIPJACK may be protected by patents, and licensing from the NSA
may be required for its use, at least in the U.S..
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: PGP and Sendmail, remailer help please
Date: Tue, 25 Jan 2000 16:07:52 GMT
Hi
I would like to set up a system whereby a plaintext email
is sent to a Linux (Debian) box running Sendmail. The message must
then be encrypted with the public key of the recipient. Any ideas
or exixting scripts?
Thanks
Jena
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jimmy Doughan <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.security.pgp,comp.security.pgp,comp.security.pgp.discuss
Subject: Re: "Trusted" CA - Oxymoron?
Date: Tue, 25 Jan 2000 12:05:16 -0500
Online Certificate Status Protocol, A realtime status check, usually done to an
issuing CA or a Validation Authority (VA) It is much more safer than a CRL,
which could be several days old (or worse). Some VAs don't actually do a
realtime status check and check CRLs.
The Vetting (checking of presented credentials) process is the most critical
part of a secure PKI. Many PKI providers force their "policy" onto the customer,
even if it may not be appropriate. A PKI should be scalable and flexible enough
to allow a wide variety of vetting procedures. AOL certainly does not have the
manpower to personally vet (approve) every single user, but they can snail mail
each user a passphrase that will start the cert retreival process. The Pentagon,
or the CIA, will need to manually approve each certificate request. As a PKI
user, you would trust a CIA certificate more than one issued by AOL. This begs
the question: How do you let people outside the organization know that you are a
secure operation?
Perhaps Standard and Poors or Dun & Bradstreet could include a security quotient
for certs issued by a particular company. As part of a OCSP lookup, a signed
response (included in a realtime OCSP request) from D&B could include a level
of security associated with the cert.
Jim Bennett wrote:
> If you trusted ABC company, that would be fine for their employees. So if
> ABC company was Wells Fargo Bank, you could be confident they were using
> decent authentication procedures.
>
> But for the individual not involved with a large well known company, what
> can you do? I'm not as concerned with spoofing as with an imposter creating
> a brand new cert using your identity. If an ISP was the sub-CA, would they
> make sure that their subscriber was who he said he was? And if so, how?
>
> Also, what is OCSP?
>
> Jim
>
> Jimmy Doughan <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Jim, how about pushing the trust down to the cert holder's company. Let's
> say I
> > hold a cert from ABC company, you should be able to authenticate directly
> to the
> > issuing CA or VA via OCSP (if the majority of PKI vendors ever adopt
> OCSP). For
> > home users' they should authenticate to their online or internet service.
> These
> > companies should have their CAs signed by one of the widely known
> certification
> > authorities (versign, Thawte, Xcert, Entrust, Baltimore) to establish
> trust.
> > It would be near impossible to spoof a cert and the issuing CA using
> OCSP. The
> > value of a Thawte chaining cert would diminish greatly using this model
> though.
> >
> > Jimbo
> >
> > Jim Bennett wrote:
> >
> > > I have been reviewing the Certification Practice Statements of various
> > > issuers of X.509 digital certificates for S/Mime email. I have been
> trying
> > > to find one that really tries to verify the identity of the certificate
> > > applicant and will do it for the general public. I haven't been too
> thrilled
> > > with what I found.
> > >
> > > Why do I care? If you are going to use a personal digital certificate
> for
> > > signing an email that has significant legal implications, like a request
> to
> > > withdraw $100,000 from your bank and have the funds wired somewhere
> else,
> > > you sure as hell want to make sure the person who has signed the message
> is
> > > really the person he says he is.
> > >
> > > Now let's see how various vendors have attacked the problem.
> > >
> > > VERISIGN (www.verisign.com)- The best you can get from them is a
> requirement
> > > that you respond to a challenge email sent to the email address you have
> > > asserted is yours. Well, whoopee. Anyone with access to your POP inbox
> can
> > > assert they are you. Value: minimal.
> > >
> > > THAWTE (www.thawte.com)- Your identity must be vouched for by a group of
> > > people whom Thawte has determined are trustworthy. How does Thawte
> determine
> > > this? If you have had your identity vouched for a selected number of
> times
> > > by different people, you are considered capable of vouching for other
> > > people's identity. Better than Verisign, but not much. A group of
> several
> > > co-conspirators could vouch for false identities for each other fairly
> > > easily. Value: still not good enough for a high value transaction.
> > >
> > > USERTRUST (www.usertrust.com) - Better. These guys will do a background
> > > check on you to try to confirm your identity claims, and will arrange
> for
> > > you to buy a fidelity bond to cover people who rely on your certificate.
> But
> > > they are currently only doing this for "contracted projects", which to
> me
> > > sounds like big jobs.
> > >
> > > PGP - You have to trust the key signers, but if you are dealing with a
> > > stranger, you are unlikely to know any of the key signers. Value:
> usually
> > > zero, occasionally good.
> > >
> > > Does anyone know of a CA who will do what UserTrust claims to do, but on
> an
> > > individual basis for the general public?
> > >
> > > Thanks,
> > >
> > > Jim Bennett
> > > Offshore Asset Protection Lawyer
> > > http://www.jim-bennett.com
> > > [EMAIL PROTECTED]
> > > [EMAIL PROTECTED]
> > > PGP public key at http://www.jim-bennett.com/about/pgp.htm
> >
------------------------------
From: Sander Vesik <[EMAIL PROTECTED]>
Subject: Re: What about the Satanic Seven???
Date: 25 Jan 2000 17:05:01 GMT
Paul Koning <[EMAIL PROTECTED]> wrote:
> None to speak of. On the other hand, if someone in another country
> (with no restrictions of its own) uses your open source code to create
> a new product, then that new product is still not allowed to go to the
> bad seven. So, in theory at least, it puts a barrier in the way of
> their getting finished products.
Huh? Person A exports code under licence XYZ from the US. Person B in
country KPT dowloads it, finds it to be a fine peice of software.
He make a crypto app and puts that on his own page (located outside
the US).
What you are saying is that person B *MUST* make sure it does not
go to one of the bad countries?
That means that you cannot export GPL-ed crypto software from the US
("no additional restrictions")?
What about person C - who never has downloaded anything from the US,
and only downloads from B-s pages?
> paul
--
Sander
There is no love, no good, no happiness and no future -
these are all just illusions.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Reversibly combining two bytes?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 25 Jan 2000 17:05:40 GMT
Alan Lawrence <[EMAIL PROTECTED]> wrote:
[Terry Ritter suggested the use of a randomly-constructed Latin Square]
: Latin squares can, in effect, hold the details of how to encrypt and
: decrypt by _any_ reversible method, i.e. one could construct a Latin
: Square, the output of which is equal to the sum of the column number and
: row number. Obviously a Latin square with no simple relationships, and
: non-linear combining is far superior....however how do I generate such a
: square? If I find suitable seeds for a random number generator, I can
: permute the sequence 0..255 to generate a column of the table, and do this
: 256 times, but then how do I make sure each number appears exactly once in
: each row as well? Admittedly one could brute force this, repeatedly
: generating the table until it works, but being fussy I don't like doing it
: that way:-)
The problem is perhaps not /quite/ as bad as you make out.
Here's one (probably highly sub-optimal) way of doing it:
As you say, you can generate a single column of 256 bytes which is a
permutation - by repeatedly swapping individual entries at random a large
number of times.
Generate one column first - by swapping lots of random rows entries.
On subsequent colums, swap random row entries, with the constraint that
you never swap a number into the same position as it is in, in any of
the previous entries in that row.
Repeat until done.
This will produce a rather random Latin Square. Of course, there is
*some* chance that this will be a linear table - but in a 256x256 table,
this chance is pretty remote.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
How do you tell when you've run out of invisible ink?
------------------------------
From: Sander Vesik <[EMAIL PROTECTED]>
Subject: Re: What about the Satanic Seven???
Date: 25 Jan 2000 17:16:29 GMT
Terje Elde <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, John E. Kuslich wrote:
>>Is it not obvious to anyone with a brain (or even perhaps the people who
>>write these regs) that people in the seven dirty nations can get
>>whatever they want by well known means if it is otherwise available on
>>the Internet?
>>
>>What am I missing here? The emperor really has no clothes, right???
> If you consider only software, then yeah, the emperor is quite nude,
> however I sustect the regulations are they way they are so that the US
> government can crack down on people exporting military grade crypto
> hardware to those countries.
> It's all or nothing, so this is the way it has to be if they want to be
> able to do that.
Errr.... Is one of the AES candidates implemented in FPGA 'military
grade crypto'? What keeps a person from inside one of the bad seven
away from that?
If they can't be bothered to get a 486 (or better) PC, free web
downloadable software and a suitcase full of ISP FPGAs... well,
then they definately do deserve what they get.
> Terje Elde
> --
> Hi! I'm a .signature virus! Copy me into your ~/.signature to help me
> spread!
--
Sander
There is no love, no good, no happiness and no future -
these are all just illusions.
------------------------------
From: [EMAIL PROTECTED] (Michael Wojcik)
Subject: Re: simplistic oneway hash
Date: 25 Jan 2000 16:29:15 GMT
Reply-To: [EMAIL PROTECTED]
In article <86b2kf$e2$[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes:
> [EMAIL PROTECTED] wrote:
> > Schneier says "no weaknesses in MD2 have been found", and cites a
> > 1993 study. Has something been discovered since then?
> Yes. RSA Labs now recommends against using it. See:
> ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf
Thanks for the pointer (though I do wish RSA Labs would make these
documents available in HTML, instead of that accursed PDF format).
In case anyone is interested: It's been found that if the checksum
step of MD2 is omitted, collisions can be found for some 16-byte
inputs (for some particular compression function IVs, including the
one given in the MD2 spec). So far, the checksum has prevented
finding "full" collisions, and determining preimages has been
difficult, but RSA recommends against using MD2 in new applications.
This isn't a problem for my application, obviously, since 1) I don't
really care about security, 2) there are well-known attacks against
my application that are almost certainly easier (like patching the
code), and to a much lesser extent 3) my application greatly restricts
the input, which makes finding collisions much harder.
Were I writing a new application that needed a real cryptographic
hash (which I wouldn't be, since I'm not an expert), I'd probably use
SHA-1 or RIPEMD, and not MD2 (and certainly not an unvetted variant
of it).
But it's an interesting document nonetheless.
--
Michael Wojcik [EMAIL PROTECTED]
AAI Development, MERANT (block capitals are a company mandate)
Department of English, Miami University
Q: What is the derivation and meaning of the name Erwin?
A: It is English from the Anglo-Saxon and means Tariff Act of 1909.
-- Columbus (Ohio) Citizen
------------------------------
From: [EMAIL PROTECTED] (Taekyoung7)
Subject: finding gcd in the large multiplicative group...
Date: 25 Jan 2000 17:28:15 GMT
Hi, all...may somebody answer my stupid question. Thanks...^^;
Finding g.c.d. in the large multiplicative group is trivial,am I right?
For example, if we have g^x*g^y1, g^x*g^y2, g^x*g^y3,...,g^x*g^yn (mod p)
where g is a generator of a multiplicative group Zp^* and we try to find the
gcd through the Euclidean algorithm, then...does the g.c.d.of them converge to
g^x with n in its reasonable size. Am I right? (please note that x is chosen
once at random and each y^i are also chosen at random in [2,p-1].)
Thanks in advance...
------------------------------
From: [EMAIL PROTECTED] (David Eppstein)
Subject: Re: Java's RSA implimentation
Date: 25 Jan 2000 09:21:44 -0800
[EMAIL PROTECTED] (Paul Schlyter) writes:
> If there are no way to copy the array (except in a loop where each
> array element is copied, one by one), arrays aren't first class
> citizens in the language. That's the situation in C and C++.
You can copy an array in C/C++ by encapsulating it in a struct.
But of course the actual hardware has to go through a loop copying each
element one-by-one; that's kind of unavoidable.
I'm also a little unsure why you think there's a big semantic difference
between a syntax that lets you directly assign one array to another
and a syntax that lets you call say memcpy.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: [EMAIL PROTECTED] (Troed)
Subject: Court cases on DVD hacking is a problem for all of us
Reply-To: [EMAIL PROTECTED]
Date: Tue, 25 Jan 2000 17:43:23 GMT
http://slashdot.org/article.pl?sid=00/01/25/0827258
This has the potential to stop a lot of what is being done in the
cryptographic industry. What Jon and a few others did was to reverse
engineer an existing crypto algorithm, find out its weaknesses, and
then use and publish their knowledge.
Question yourselves - how many of us professional and hobbyist
cryptographers haven't reverse engineered crypto algorithms?
I have.
Jon Johansen also did - and then found out that Hollywood used their
influenses to get the Norwegian government to take him in for
questioning, sieze his equipment, threatening him (and his father)
with several years in prison.
Do what you feel needs to be done - especially those of you that are
"well known names in the industry".
___/
_/ - in support of Jon Johansen
Also, more info on http://www.opendvd.org
------------------------------
From: [EMAIL PROTECTED] (Michael Wojcik)
Subject: Re: Reversibly combining two bytes?
Date: 25 Jan 2000 17:04:53 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Alan
Lawrence <[EMAIL PROTECTED]> writes:
> Latin squares can, in effect, hold the details of how to encrypt and
> decrypt by _any_ reversible method, i.e. one could construct a Latin
> Square, the output of which is equal to the sum of the column number and
> row number. Obviously a Latin square with no simple relationships, and
> non-linear combining is far superior....however how do I generate such a
> square? If I find suitable seeds for a random number generator, I can
> permute the sequence 0..255 to generate a column of the table, and do this
> 256 times, but then how do I make sure each number appears exactly once in
> each row as well? Admittedly one could brute force this, repeatedly
> generating the table until it works, but being fussy I don't like doing it
> that way:-)
Just off the top of my head:
Generate one permutation 0..255. Call it P.
Generate a second permuation 0..255. Call it R.
For each column C[i=0..255], rotate P by R[i]. The rotation can be
trivially computed while populating C by using (index + R[i]) mod 256
to index P.
For example:
int P[256], R[256], C[256][256];
GeneratePermutation(P);
GeneratePermutation(R);
int col, row;
for (col=0; col < 256; col++)
for (row=0; row < 256; row++)
C[col][row] = P[ (row + R[col]) % 256 ];
Since all columns are different rotations of the same permutation,
no two columns will be the same, and no two columns will have the
same value x in a given row r, so no row will have a repeated
value.
I've only given this cursory thought; it may be broken or weak.
--
Michael Wojcik [EMAIL PROTECTED]
AAI Development, MERANT (block capitals are a company mandate)
Department of English, Miami University
This is a "rubbering action game," a 2D platformer where you control a
girl equipped with an elastic rope with a fishing hook at the end.
-- review of _Umihara Kawase Shun_ for the Sony Playstation
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To:
alt.anarchism,alt.computer.security,alt.security,alt.security.espionage,alt.security.pgp
Subject: Re: 1on1lite (Was: Re: Echelon monitors this group)
Date: Tue, 25 Jan 2000 11:24:24 -0600
In article <[EMAIL PROTECTED]>, "An Anarchist"
<[EMAIL PROTECTED]> wrote:
> ps. The problem with writing software is that ones you finished someone
> writes a better one within a few days and you have to start all over again.
> You can never write perfect code there always will be a better way of doing
> things, or in this case a more secure one.
if yo are always doing code without a clear concept of what security you
are after, and a clear realisation of what is possible, you are always
going to be putting out security fires. Security is going to mean some
sort of restrictions, especially against doing trendy things that are
incompatible with it.
Efforts to do things right are to be rewarded, but they must be weighed
against concurrent efforts that might tend to undermine security before we
can pass along any attaboys.
--
About injustice, the stronger I get the meaner I feel, or is it the
other way around. Do not respect sacred cows that seek to trample you while preaching
about the good they do.
------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Subject: Re: "Trusted" CA - Oxymoron?
Date: 25 Jan 2000 18:25:28 GMT
In article <[EMAIL PROTECTED]>, Jimmy Doughan <[EMAIL PROTECTED]> writes:
>This begs
>the question: How do you let people outside the organization know that you
>are a
>secure operation?
By having an audit from an external organization that is generally trusted,
like price-waterhouse or KPMG.
The CPS (Certificate Practices Statement) should indicate how (if) they verify
the identity of an applicant for a certificate. That's one key piece of a
relying party's judgement on the value of that certificate. Other pieces are
the security of the CA, it's operating procedures, etc.
The external audit tells the world that the CA operator is living up to his
CPS, operations specifications, and other "promises".
And even the CIA will be likely to have an external audit... maybe by GAO,
maybe by a public firm.
In our PKI plans we budget for quarterly internal audits, and an annual
external audit by one of the "big five" firms.
Timothy Metzinger
Commercial Pilot - ASEL - IA AOPA Project Pilot Mentor
DOD # 1854 '82 Virago 750 - "Siobhan"
Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Does RSA use real prime ?
Date: Tue, 25 Jan 2000 18:22:11 GMT
> So I repeat. If p or q are not prime, encryption/decryption will not
> work for the most part [it may work once with a slight possibility].
> So you must find new primes.
So are you saying that all one has to do is randomly select a p
and a q and try to encrypt and then decrypt some random data say
a half dozen times and if it works well, then p & q are useable?
I have never heard of this relationship you are describing before.
--
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
http://www.ciphermax.com/book
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: Tue, 25 Jan 2000 12:25:11 -0600
r.e.s. wrote:
>
> I'm trying to follow up on your earlier suggestions involving
> polynomials primitive on GF(2) and GF(5).
>
> Can you point me to any source for the primitive trinomials
> on GF(5) up to degree ~50? (I've found these for GF(2).)
I doubt there's any literature for that. I do have some software
which could easily be modified to look for them. In its present
invocation it's overkill, but it can find irreducible trinomials.
To prove they are primitive, you'll have to factor 5^n-1 and use
each irreducible trinomial as the modulus, and find x^r for all
combinations of the factors. The paper mentioned earlier in the
thread tells how to that efficiently.
Send me e-mail via [EMAIL PROTECTED] and I'll be happy to send
the code and explain what you'll have to do to get what you're
looking for.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Does RSA use real prime ?
Date: Tue, 25 Jan 2000 18:35:08 GMT
> First off the primality testing on PGP is such that the
> odds of you winning the lottery jackpot within 5 seconds
> of being struck by lightning is a much more likely
> occurence than a PGP chosen pair of primes containing
> a composit number.
And how remote is that? Is it as remote as someone winning the
lottery in CA twice in one decade? That has happened. :)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Modem Crypto (Military Grade)
Date: 25 Jan 2000 09:50:31 -0800
In article <[EMAIL PROTECTED]>, "Steve says...
>
>I'm looking for a modern device that can use a 33k modem (analog lines)
>for a dialup solution
[snip]
>
>The analog portion of even the ISDN STU can only do 9.6k max, which is all
>right for a BBS application, but inadequate for PPP.
If you're doing PPP, you could use encryption at a higher level in the
protocol. IPSec could run on a small SBC, I'm sure, and that would give
more flexibility.
>Has anyone worked with a more modern analog line device?
http://www.commdevices.com/ has one that handles 3DES transparently.
Cheers,
Steve
--
-- Steve Atkins -- [EMAIL PROTECTED]
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Does RSA use real prime ?
Date: Tue, 25 Jan 2000 18:45:35 GMT
> The odds that a prime generated by PGP is not really prime
> are lower than the chance that a meteor will crash into the
> Earth and extinguish all life on the planet before you can
> finish reading this reply.
Well, I was going to ask you how remote of a chance that would
be, but then I realized that even if a meteor did hit the earth,
the time it would take for the event to extinguish all life
would be greater than the time it took me to finish reading
your post. :)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Transposition over ASCII-coded text
Date: Tue, 25 Jan 2000 12:47:51 -0600
wtshaw wrote:
> In spite of the beauties of the internet and its reasonably dependable
> commonication, with the recovery of my right hand being noticable in the
> last month, I have dusted off the ole rig and am looking forward to 30m
> one day soon. Some things are deep passions, hamming and crypto, to name
> two.
Too bad you can't do them at the same time :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Jim Reeds)
Subject: Re: RNG for OTPs during WWII
Date: Tue, 25 Jan 2000 18:49:40 GMT
In article <[EMAIL PROTECTED]>, Jim Reeds <[EMAIL PROTECTED]>
wrote about the German Foreign Office one time pad system in WWII, called by
the Allies "Floradora":
|> ... There was a
|> lecture on the subject at the last-but-one Cryptologic History Symposium.
|> I have spoken with a member of the Arlington Hall team that worked on the
|> project.
|>
There is a web page summary of this talk at
http://intelligence-history.wiso.uni-erlangen.de/newsl-5-2.htm
which contains some details I had forgotten.
Search for "Floradora" to find the relevant passage. (After reading it I
see that I have in fact spoken with TWO members of the team, albeit briefly.)
--
Jim Reeds, AT&T Labs - Research
Shannon Laboratory, Room C229, Building 103
180 Park Avenue, Florham Park, NJ 07932-0971, USA
[EMAIL PROTECTED], phone: +1 973 360 8414, fax: +1 973 360 8178
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: finding gcd in the large multiplicative group...
Date: Tue, 25 Jan 2000 12:55:12 -0600
Taekyoung7 wrote:
>
> Hi, all...may somebody answer my stupid question. Thanks...^^;
>
> Finding g.c.d. in the large multiplicative group is trivial,am I right?
>
> For example, if we have g^x*g^y1, g^x*g^y2, g^x*g^y3,...,g^x*g^yn (mod p)
> where g is a generator of a multiplicative group Zp^* and we try to find the
> gcd through the Euclidean algorithm, then...does the g.c.d.of them converge to
> g^x with n in its reasonable size. Am I right? (please note that x is chosen
> once at random and each y^i are also chosen at random in [2,p-1].)
I'd bet g^x*g^r. If n is "reasonable" then you'll have lots of common
factors in the y's, which I call r. So it boils down to gcd(y1, y2,
...)
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
