Cryptography-Digest Digest #920
Cryptography-Digest Digest #920, Volume #13 Fri, 16 Mar 01 18:13:01 EST
Contents:
Re: Factoring RSA (br)
Re: Factoring RSA (br)
Re: Q: IP (Ben Cantrick)
Re: NTRU - any opinions (Paul Rubin)
Re: An extremely difficult (possibly original) cryptogram (Jim Gillogly)
Re: How to eliminate redondancy? (SCOTT19U.ZIP_GUY)
Re: Factoring RSA (Jeffrey Williams)
Re: Factoring RSA ("Dann Corbit")
Re: Q: IP (Vernon Schryver)
Re: PKI and Non-repudiation practicalities (Anne Lynn Wheeler)
Re: Factoring RSA (br)
Re: Factoring RSA ("Tom St Denis")
From: br [EMAIL PROTECTED]
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 16:07:04 -0400
You wrote :
"I can't say that I really understand how your algorithm works, since S
does not change during the iterations. Perhaps I fail to understand
some
fundamental piece of the algorithm.
Suppose as sample n=1633
you have to try gcd( (10^1633)- 1,1633)
gcd( (10^1632)-1,1633)
etc... until S= (10^816) - 1
Is it clear?
--
From: br [EMAIL PROTECTED]
Subject: Re: Factoring RSA
Date: Fri, 16 Mar 2001 16:08:35 -0400
The algo is not practical for small numbers.
Dann Corbit wrote:
"br" [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED]...
Try this algo to factor N.
Let S= (10^k) - 1
for k=N to (n/2) step -1
Let c=gcd(S,N)
if c1 or cN then c is a solution.
It's hard to compute hudge number. But with computers able to manage a
hudge number, it's feasible.
Do yourself a favor and only test odd numbers. Doubles the speed of the loop.
Here is an efficient GCD, with a nice Maple implementation:
http://citeseer.nj.nec.com/cache/papers2/cs/5083/http:zSzzSzwww.math.ncsu.eduz
Sz~kaltofenzSzbibliographyzSz99zSzKaMo99.pdf/kaltofen99genericity.pdf
I can't say that I really understand how your algorithm works, since S does
not change during the iterations. Perhaps I fail to understand some
fundamental piece of the algorithm.
I once had a similar notion, except that I took a product of known primes up
to some K. For instance, if you form a product of all primes from 2 up to the
largest prime in [0..2^32] then GCD of that product with any number up to
2^64th will partly factor it unless it is prime.
However, this is a horrible algorithm and not at all impractical.
Have you had a look at Chris Cauldwell's prime page?
He lists some very efficient techniques for factoring.
Even so, it is very expensive to factor large numbers. A product of two large
primes is dauntingly difficult to factor. The RSA challenges (for instance)
very effectively show that it is not cost effective to try to break RSA for
even modest modulus sizes.
If you look at the actual CPU hours, it is a stupefying total. And the
algorithms used are among the best known for problems in that particular size
range.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
--
From: [EMAIL PROTECTED] (Ben Cantrick)
Subject: Re: Q: IP
Date: 16 Mar 2001 14:13:27 -0700
In article [EMAIL PROTECTED],
Mok-Kong Shen [EMAIL PROTECTED] wrote:
Thanks for the informations. I asked the question because
I read a newspaper article saying that having a fixed IP
means that attackers have a fixed target to work on, while
with dynamically assigned IPs one is rather anonymous, being
only one element of a more or less large set belonging
to the same ISP, and is thus advantageous in that respect.
In case this statement of the newspaper is incorrect, please
kindly tell.
Well... it's kind of like saying that if you worked in a different
office every day, you wouldn't ever get mugged going home.
You are a small bit safer using a dynamic IP. But I wouldn't
depend on it as a safety measure. A dynamic IP is no guarantee of
safety.
-Ben
--
Ben Cantrick ([EMAIL PROTECTED])| Yes, the AnimEigo BGC dubs still suck.
BGC Nukem: http://www.dim.com/~mackys/bgcnukem.html
The Spamdogs: http://www.dim.com/~mackys/spamdogs
"I took an IQ test once." "Yeah?" "The results came back negative."
--
From: Paul Rubin [EMAIL PROTECTED]
Subject: Re: NTRU - any opinions
Date: 16 Mar 2001 13:21:40 -0800
Robert Harley [EMAIL PROTECTED] writes:
Generating a 113-bit curve for short-term security e.g., for
key-exchange in the WAP standard, takes 8 seconds with just a
StrongARM chip and 36 K of RAM.
Very good work with the point counting. But why is WAP key exchange
short term security? Doesn't it need forward secrecy?
--
From: Jim Gillogly [EMAIL PROTECTED]
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Cryptography-Digest Digest #920
Cryptography-Digest Digest #920, Volume #12 Sat, 14 Oct 00 05:13:01 EDT Contents: Cryptography FAQ (06/10: Public Key Cryptography) ([EMAIL PROTECTED]) Cryptography FAQ (07/10: Digital Signatures) ([EMAIL PROTECTED]) Crossposted-To: talk.politics.crypto,sci.answers,news.answers,talk.answers Subject: Cryptography FAQ (06/10: Public Key Cryptography) From: [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] Date: 14 Oct 2000 08:37:54 GMT Archive-name: cryptography-faq/part06 Last-modified: 94/06/07 This is the sixth of ten parts of the sci.crypt FAQ. The parts are mostly independent, but you should read the first part before the rest. We don't have the time to send out missing parts by mail, so don't ask. Notes such as ``[KAH67]'' refer to the reference list in the last part. The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography FAQ is posted to the newsgroups sci.crypt, talk.politics.crypto, sci.answers, and news.answers every 21 days. Contents: 6.1. What is public-key cryptography? 6.2. How does public-key cryptography solve cryptography's Catch-22? 6.3. What is the role of the `trapdoor function' in public key schemes? 6.4. What is the role of the `session key' in public key schemes? 6.5. What's RSA? 6.6. Is RSA secure? 6.7. What's the difference between the RSA and Diffie-Hellman schemes? 6.8. What is `authentication' and the `key distribution problem'? 6.9. How fast can people factor numbers? 6.10. What about other public-key cryptosystems? 6.11. What is the `RSA Factoring Challenge?' 6.1. What is public-key cryptography? In a classic cryptosystem, we have encryption functions E_K and decryption functions D_K such that D_K(E_K(P)) = P for any plaintext P. In a public-key cryptosystem, E_K can be easily computed from some ``public key'' X which in turn is computed from K. X is published, so that anyone can encrypt messages. If decryption D_K cannot be easily computed from public key X without knowledge of private key K, but readily with knowledge of K, then only the person who generated K can decrypt messages. That's the essence of public-key cryptography, introduced by Diffie and Hellman in 1976. This document describes only the rudiments of public key cryptography. There is an extensive literature on security models for public-key cryptography, applications of public-key cryptography, other applications of the mathematical technology behind public-key cryptography, and so on; consult the references at the end for more refined and thorough presentations. 6.2. How does public-key cryptography solve cryptography's Catch-22? In a classic cryptosystem, if you want your friends to be able to send secret messages to you, you have to make sure nobody other than them sees the key K. In a public-key cryptosystem, you just publish X, and you don't have to worry about spies. Hence public key cryptography `solves' one of the most vexing problems of all prior cryptography: the necessity of establishing a secure channel for the exchange of the key. To establish a secure channel one uses cryptography, but private key cryptography requires a secure channel! In resolving the dilemma, public key cryptography has been considered by many to be a `revolutionary technology,' representing a breakthrough that makes routine communication encryption practical and potentially ubiquitous. 6.3. What is the role of the `trapdoor function' in public key schemes? Intrinsic to public key cryptography is a `trapdoor function' D_K with the properties that computation in one direction (encryption, E_K) is easy and in the other is virtually impossible (attack, determining P from encryption E_K(P) and public key X). Furthermore, it has the special property that the reversal of the computation (decryption, D_K) is again tractable if the private key K is known. 6.4. What is the role of the `session key' in public key schemes? In virtually all public key systems, the encryption and decryption times are very lengthy compared to other block-oriented algorithms such as DES for equivalent data sizes. Therefore in most implementations of public-key systems, a temporary, random `session key' of much smaller length than the message is generated for each message and alone encrypted by the public key algorithm. The message is actually encrypted using a faster private key algorithm with the session key. At the receiver side, the session key is decrypted using the public-key algorithms and the recovered `plaintext' key is used to decrypt the message. The session key approach blurs the distinction between `keys' and `messages' -- in the scheme, the message includes the key, and the key itself is treated as an encryptable `message
Cryptography-Digest Digest #920
Cryptography-Digest Digest #920, Volume #10 Mon, 17 Jan 00 22:13:01 EST
Contents:
Re: Password example encrypt/dycrypt! (Pelle Evensen)
Re: Why is EDI dead? Is S/MIME 'safe'? Who and why? (Richard A. Schulman)
how to encipher (Christopher)
Re: Cracking an ADFGVX cipher ("Douglas A. Gwyn")
Re: New Crypto Regulations ("Douglas A. Gwyn")
Re: New Crypto Regulations ("Douglas A. Gwyn")
Re: If enough is good, why is more better ? Re: Triple-DES and NSA??? (John Savard)
Re: New Crypto Regulations (John Savard)
Re: New Crypto Regulations (Johnny Bravo)
Re: Suitable hash for this application - in the public domain? (drickel)
Re: Forward secrecy for public key encryption (lcs Mixmaster Remailer)
Re: Questions about message digest functions ([EMAIL PROTECTED])
Re: crypt() (Bill Unruh)
Re: Cracking an ADFGVX cipher (GJJ)
Announce: Puffer 3.10 (Kent Briggs)
Re: Why is EDI dead? Is S/MIME 'safe'? Who and why? (James Redfern)
From: Pelle Evensen [EMAIL PROTECTED]
Subject: Re: Password example encrypt/dycrypt!
Date: Mon, 17 Jan 2000 22:30:02 +0100
[EMAIL PROTECTED] wrote:
You can find the MDx, SHA-1 and others at
ftp://ftp.funet.fi/pub/crypt/hash/
You've missed one - the Message Authenticator Algorithm is, as far as I'm
aware, the first Cryptographic Hash Function or Message Digest to gain
widespread acceptance. It has become a part of ISO standard 8731-2:
Approved Algorithms for Message Authentication. Even Applied Cryptography
fails to acknowledge its historical importance.
As it seems to be unavailable in electronic form, I've put HTML and PDF
versions on my web site.
http://www.cix.co.uk/~klockstone
The point was to show something that is reasonable to use in practice,
not to provide a good historical account of hash functions. :-)
From section 2 in the paper;
"When a well designed authenticator is used, giving a 32 bit result,
the probability that a message alteration will not be detected is 2^-32,
which is small enough for most purposes."
Even if MAA is cryptographically strong, which we for the sake argument
can assume, 32 bits is much too small to be useful for anything but
perhaps ordinary hash table lookups. For hashing passwords, 32 bits is
close to as bad as not doing any hashing at all.
Regarding widespread acceptance, RFC1321 (MD5) has probably been just as
widely "accepted" for usage as a one way hash function. :-)
/Pell
==
Pelle Evensen [EMAIL PROTECTED] Telenordia AB/Algonet
http://www.evensen.org for public key.KeyID: 0xDCACD9A1
Public key fingerprint 22DC 520D 7E00 F79C 8BEB F055 1E8C 715E
--
From: Richard A. Schulman [EMAIL PROTECTED]
Crossposted-To: comp.security.misc,alt.security.pgp
Subject: Re: Why is EDI dead? Is S/MIME 'safe'? Who and why?
Date: Mon, 17 Jan 2000 18:01:29 -0500
Reply-To: [EMAIL PROTECTED]
On Tue, 18 Jan 2000 04:32:43, [EMAIL PROTECTED] (Padgett
0sirius) wrote:
Electronic Data Interchange or communications with people you know is =
being=20
subhumed into Electronic Commerce.=20
EDI comprises batch data exchange between companies. The information
exchanged need not (and often does not) consist of a purchase or sale.
E-commerce consists of individual transactions between purchasers
(usually consumers) and sellers (usually retailers).
---
Richard Schulman
To email me, remove the "XYZ"
--
From: [EMAIL PROTECTED] (Christopher)
Subject: how to encipher
Date: Mon, 17 Jan 2000 23:12:54 GMT
Hi,
I am a beginner. I use p=20507,q=55889, e=67.
So if I only obtain n=pq=1146115723 and e=67. I have find the private
key from the public key, private key is d=85525323.
Pls tell me how to decipher a text use d,
since M^d mod n, M and d is too large handle is my computer.
Thanks
--
From: "Douglas A. Gwyn" [EMAIL PROTECTED]
Subject: Re: Cracking an ADFGVX cipher
Date: Mon, 17 Jan 2000 23:05:52 GMT
John Savard wrote:
The account of how the original ADFGX cipher was broken in David
Kahn's book "The Codebreakers" is the only one I'm familiar with,
I vaguely recall that Friedman's monograph on the subject had been
declassified and released to the National Archives. But I could be
mistaken..
--
From: "Douglas A. Gwyn" [EMAIL PROTECTED]
Subject: Re: New Crypto Regulations
Date: Mon, 17 Jan 2000 23:12:09 GMT
John Savard wrote:
Democracy in the United States may have a bad cold, but it isn't
terminal.
To the extent that people think a democracy is desirable,
the US ideal of government that promotes individual rights
has already died.
--
From: "Douglas A. Gwyn" [EMAIL PROTECTED]
Subject: Re: New Crypto Regulations
Date: Mon, 17 Jan 2000 23:16:48 GMT
John Savard wrot
Cryptography-Digest Digest #920
Cryptography-Digest Digest #920, Volume #9 Wed, 21 Jul 99 16:13:02 EDT
Contents:
Re: Replacing IDEA with Blowfish ([EMAIL PROTECTED])
The best utility to restore PARADOX PASSWORDS (CryptoExplorations Lab.)
Re: Cluelessness Alert? I'm Not So Sure. (latest Crypto-Gram) (John Savard)
Re: NBE: Not crackable by brute force key search (John Savard)
Re: NBE: Not crackable by brute force key search (Volker Hetzer)
Re: NBE: Not crackable by brute force key search (Mickey McInnis)
SSL Implementation? ([EMAIL PROTECTED])
Re: Algorithm or Protocol? (John Myre)
Re: Length of public key in PGP? ([EMAIL PROTECTED])
Re: Crypt FAQ Comments : New Topics (Roger Carbol)
Turing's Treatise on Enigma (Frode Weierud)
Re: DES permutations ("David G. Koontz")
Re: Traffic flow confidentiality (David Wagner)
Re: Looking for RC4 alternative (Mark Leighton Fisher)
Re: How Big is a Byte? (was: New Encryption Product!) (Finder Keeper)
From: [EMAIL PROTECTED]
Subject: Re: Replacing IDEA with Blowfish
Date: Wed, 21 Jul 1999 13:16:10 GMT
In article 7n2stc$220u$[EMAIL PROTECTED],
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
In article [EMAIL PROTECTED], Paul Koning
[EMAIL PROTECTED] wrote:
[EMAIL PROTECTED] wrote:
...
3) There are designs for Blowfish in hardware, I dunno if they
have
been done yet or not. IDEA was designed for hardware and software
(somewhat).
"somewhat" is right. IDEA uses multiplication, which is expensive
in hardware (or slow). Feistel networks such as in Blowfish are
far cheaper. Then again, in the case of Blowfish the large size
of the key schedule hurts.
paul
actaully since IDEA use multiplicatiopn of a variable times a
constant
each one of those could be repacled by a small 16X16 bit S table.
which is not so expensive. Also one could could improve IDEA by
usinging a larger class of functions instead of a lowly multiply which
may make it more vulnerable to being broken.
Yes, and no. If you replace the multiplies that are done mod (2^16)+1,
it will work. However, if you change the internal multiplies, the ones
that are not done mod (2^16)+1, it will not work. I tried messing
around with that part of the cipher and nothing works. If you still
don't know which multiplies I'm talking about, just follow the key
schedule of IDEA. Only 18 of the 52 subkeys need inverses. Another 18
are used for the additions, leaving 16 subkeys which do not have to be
inverses for decryption. These 16 relate to the multiplies that you
can't change.
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
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
--
From: CryptoExplorations Lab. [EMAIL PROTECTED]
Subject: The best utility to restore PARADOX PASSWORDS
Date: Wed, 21 Jul 1999 13:46:02 GMT
Ultimate Paradox CryptoExplorer for Win9X/NT v1.7
Please visit us at http://cryptoexplorer.da.ru
- 100% guarantee that you can open and read an encrypted table or script
- Works with Paradox tables and scripts
- Supports any version of Paradox and BDE (Borland Database Engine)
which was used in Borland Delphi and Borland C++ Builder
- Allows you to check your version of Paradox/BDE for backdoors
(there are passwords which can open any encrypted object in some
versions)
- Shows you all the passwords which can open your table that helps you
find the original password (may be you need it for some reasons)
- You can also find a secret password used by Borland for a backdoor in
your version of Paradox/BDE
- Incredibly high speed much higher than in ordinary brute-force
algorithm
- You will have a working password in a few seconds
Copyright (C) 1999 CryptoExplorations Lab.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
--
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Cluelessness Alert? I'm Not So Sure. (latest Crypto-Gram)
Date: Wed, 21 Jul 1999 15:10:29 GMT
[EMAIL PROTECTED] (Roger Fleming) wrote, in part:
For example, there is no mention of validation and
auditing of site updates by 'legitimate' webmasters. You need to give careful
consideration to preventing a webmaster from accidentally uploading data he
shouldn't. (This is very tricky indeed; I suspect there isn't yet any
electronic means smart enough to cover all aspects of this). He might also do
this maliciously, so you need to be able to prove exactly who performed any
modification to the site, even if they are authorised to do so.
That certainly is an important point. There are probably many others
that I wouldn't have any idea about, but the need to
