Cryptography-Digest Digest #491, Volume #9 Sun, 2 May 99 21:13:02 EDT
Contents:
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(D. J. Bernstein)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Boris Kazak)
Hot new algorithm? ([EMAIL PROTECTED])
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: Factoring breakthrough? ("Allen Ellison")
Re: Double Encryption is Patented! (from talk.politics.crypto) (Peter Gutmann)
Re: A challenge for you ! (Jon Haugsand)
Re: Factoring breakthrough? (Paul Rubin)
Re: Hot new algorithm? (Virgil)
Re: Hot new algorithm? (Scott Fluhrer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: 2 May 1999 05:47:15 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> To minimize or "fix" the risk of catastrophic failure, we can instead
> use a "cascade" of multiple (say 3) different ciphers, each with their
> own key.
In case you haven't noticed, popular secret-key functions such as 3DES_k
are already designed as compositions of many different functions.
> So another part of my "fix package" is the ability to change ciphers
> dynamically from a pool of ciphers.
In case you haven't noticed, popular secret-key functions are already
selected dynamically from a huge pool of functions. For example, 3DES_k
is parametrized by a 168-bit key k.
---Dan
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Wed, 28 Apr 1999 18:52:38 -0400
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
>*******************
> I'm assuming the technique Ritter described, but I don't think
> whether the protocol tries to hide the choice of cipher makes
> much difference. The attacker doesn't need the general ability
> to determine what cipher is in use; he only needs to be able to
> distinguish when the cipher in use is one he can break. If he
> can break a cipher he can surely distinguish it.
>***************
Please be so kind to give a brief explanation: if there is a message
encrypted with a block cipher in 64-bit blocks, how is our cherished
attacker supposed to distinguish - was the encryption done by DES,
BLOWFISH, IDEA, 3DES, CAST or FEAL?
Thankful in advance. BNK
>
> --Bryan
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math,comp.programming,de.org.ccc
Subject: Hot new algorithm?
Date: Sun, 02 May 1999 20:49:16 GMT
This is from a friend of mine. I think it's worth reading.
Thanks for your feedback,
Manuel
===========
Numbersplit
This is a method to split up big numbers into factors taking
advantage of the 3rd binomic formula: (a-b)*(a+b)=a²+b²
I don't know if it's a new method or just an old, well-known algorithm. Please
give me an answer if you know something about that. Any product of the type
z=x*y, where x,y, and z are odd numbers, can be written as z=(a+b)*(a-b),
where a and b are integers, a=(x+y)/2 and b=(x-y)/2. Thus if we want to split
up the number z (must be odd), we take the next square number a² that is
higher then z and compute the difference a²-z. If this is also a square
number, we found the solution z=(a+b)*(a-b), where b=sqrt(a²-z). If not, we
try the next square (a+1)² and so on. This seems to be more complicated than
simply dividing the big number z by all integers between 2 and sqrt(z), but it
is effective if we use certain tricks. First of all, we compute the square
root of z using floating point operations, this should normally not last to
long. Then we take its integer part, add 1 and square it thus giving a², and
then we compute the difference a²-z and store it in an integer variable
diff=a²-z. And then we can forget the big numbers. We succesively compute the
square numbers 1,4,9,16... (this is done by the 1st binomic formula: just add
2*b+1 to b² add increment b, and you have (b+1)²) and compare it with the
difference counter. If it's equal, we found one solution. If it's less, we go
on and if it's higher, we add 2*a+1 to the difference counter and increment a
to get the new difference for the next square number. Because b is half the
difference between the to factors x and y, this method is very fast if the
factors are near to another, e.g. 57983*57997. If z is a prime number, then
it is ineffective and stops with 1*z. In this case it is easy to provoke an
overflow computing the squares, so we have still to do an improvement: If we
increment the difference counter to the next square number, we can subtract
the current b² and set this variable to zero, because the difference in
between will be the same. So the difference counter will not exceed 3*z. There
is still something we can improve; for example we can use assembler code for
the cracking and combine the subtraction and comparison: use one register as
the difference counter and subtract 2*b+1. Then the flags will show you what
to do: The zero-flag indicates, that we found a solution, the carry-flag
means, that we must use the next square number, i. e. increment the difference
counter by 2*a+1. Here is a sample C++ program that does the numbersplitting.
Please give me a feedback if you know something about this method, if it's
already known or really new or if you have improvements.
// Program that splits up big numbers into factors
// by using the binomic formula (a-b)*(a+b)=a^2-b^2
#include <iostream.h>
#include <math.h>
typedef unsigned long int bignum; // you can put here your best integer type
bignum maxtests=1<<15;
bignum z,a,b,aquad;
bignum bquad,diff;
main ()
{ cout<<"Enter a big number ";
cin>>z;
a=bignum(sqrt(z)+1); // hope that z is not a square number
aquad=a*a; // otherwise use a=bignum(sqrt(z))
b=1;bquad=1;
diff=aquad-z;
maxtests=z>>1; // do not more than z/2 tests
while ((diff!=bquad) && (b<maxtests)) { // as long as we havn't found a
while (bquad<diff) { // solution
bquad+=2*b+1; // compute next square number b²
b+=1;
}
if (diff<bquad) {
diff+=2*a+1; // compute the new difference
a+=1;
diff-=bquad;
bquad=0; // prohibit overflow
}
}
if (diff==bquad) cout<<"Solution found :"<<a-b<<"*"<<a+b<<"="<<z;
else cout<<"No solution found after "<<bignum(maxtests)<<" tests.";
// this should not appear :-)
cin.get();cin.get(); // wait for keypress
return 0;
}
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Sun, 02 May 1999 21:10:43 GMT
On 2 May 1999 05:47:15 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (D. J. Bernstein) wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>> To minimize or "fix" the risk of catastrophic failure, we can instead
>> use a "cascade" of multiple (say 3) different ciphers, each with their
>> own key.
>
>In case you haven't noticed, popular secret-key functions such as 3DES_k
>are already designed as compositions of many different functions.
That's fine, but Triple-DES is just *one* particular 3-level
metacipher. The same idea, using thousands of ciphers, would produce
billions of different metaciphers. Many of these ciphers will be
structurally different, and will require different attacks.
The advantage is the ability to change ciphers frequently, "at
random." In this way we terminate any successful secret attack on our
cipher, if such an attack does exist and is being carried out. The
alternative of using any one cipher repeatedly means that if a
successful attack is being applied, it will continue to be applied,
and will expose past, present, and future data.
Cryptanalysis of any length by experts of even the best talent and
education cannot guarantee us that no successful attack exists. But
cryptography users *can* act to minimize loss, to limit the Opponents'
success and to reduce their payoff, simply by changing ciphers
frequently. And if we use a growing body of ciphers, we additionally
force our Opponents into making large expenditures to get even these
reduced payoffs.
The alternative is to not act, to use the same cipher repeatedly
because it is "thought" to be strong, thus placing all our data at the
risk of a "thought" consensus which has no scientific certainty. The
best cryptanalysis can do is to give an upper bound to strength, which
is not good enough for me.
>> So another part of my "fix package" is the ability to change ciphers
>> dynamically from a pool of ciphers.
>
>In case you haven't noticed, popular secret-key functions are already
>selected dynamically from a huge pool of functions. For example, 3DES_k
>is parametrized by a 168-bit key k.
As far as I know, the strength of Triple-DES is *not* even *thought*
to be 168 bits. Most modern attacks are made against the structure of
a cipher, and not the keyspace. Being able to attack one cipher does
not mean that one can attack any cipher.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 2 May 1999 05:00:35 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: "Allen Ellison" <[EMAIL PROTECTED]>
Subject: Re: Factoring breakthrough?
Date: Sun, 2 May 1999 15:15:28 -0600
Israeli Scientist Reports Discovery of Advance in Code Breaking
By JOHN MARKOFF
New York Times
An Israeli computer scientist is expected to shake up the world of
cryptography this week when he introduces a design for a device that could
quickly unscramble computer-generated codes that until now have been
considered secure enough for financial and government communications.
In a paper to be presented Tuesday in Prague, the computer scientist, Adi
Shamir, one of the world's foremost cryptographers, will describe a machine,
not yet built, that could vastly improve the ability of code breakers to
decipher codes thought to be unbreakable in practical terms. They are used
to protect everything from financial transactions on the Internet to account
balances stored in so-called smart cards.
Shamir's idea would combine existing technology into a special computer that
could be built for a reasonable cost, said several experts who have seen the
paper. It is scheduled to be presented at an annual meeting of the
International Association for Cryptographic Research, which begins on
Monday.
The name of Mr. Shamir, a computer scientist at Weizmann Institute of
Science in Rehovoth, Israel, is the "S" in R. S. A., the encryption design
that has become the international standard for secure transmissions. He is a
co-inventor of R.S.A. -- with Ronald Rivest of the Massachusetts Institute
of Technology and Leonard Adleman of the University of Southern California.
R.S.A. is known as public-key cryptography. In this system, a person has a
public key and a private key. The public key is used to scramble a message
and may be used by anyone, so it can, even should, be made public. But the
private key that is needed to unscramble the message must be kept secret by
the person who holds it.
R.S.A., like many public-key systems, is based on the fact that it is
immensely difficult and time-consuming for even the most powerful computers
to factor large numbers. But Mr. Shamir's machine would make factoring
numbers as long as about 150 digits much easier, thus making it much simpler
to reveal messages scrambled with public-key encryption methods.
A number of advances in factoring have been made in the last five years. But
most of them are the result of applying brute force to the problem.
When R.S.A. was created in 1977, Mr. Shamir and his colleagues challenged
anyone to break the code. Employing 1970's technology, they said, a
cryptographer would need 40 quadrillion years to factor a public key, and
they predicted that even with anticipated advances in computer science and
mathematics, no one would be able to break the code until well into the next
century.
In fact, a message the trio had encoded with a 129-digit key successfully
withstood attack for only 17 years. It was factored by an international team
of researchers in 1994.
Using Mr. Shamir's machine, cracking the 140-digit number would be reduced
to the difficulty of cracking a key about 80 digits long -- relatively easy
by today's standards.
Researchers said that if his machine worked it would mean that cryptographic
systems with keys of 512 bits or less -- that is, keys less than about 150
digits long -- would be vulnerable in the future, an exposure that would
have seemed unthinkable only five years ago. The longer 1,024-bit keys that
are available today would not be vulnerable at present.
DJohn37050 wrote in message
<[EMAIL PROTECTED]>...
>I have heard this rumor also, no details yet.
>Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Peter Gutmann)
Subject: Re: Double Encryption is Patented! (from talk.politics.crypto)
Date: 2 May 1999 20:23:57 GMT
[EMAIL PROTECTED] (John Savard) writes:
>However, I noticed something else interesting. It notes that the Australian
>government had developed something called SENECA, as a "replacement" for
>DES.
>If this was indeed intended for civilian use, was the algorithm ever made
>public?
It was developed (AFAIK) by the Australian DSD and seems to have pretty much
sunk without a trace after the initial announcements (although no doubt
there's still all manner of legacy hardware lying around which uses it).
Peter.
------------------------------
From: Jon Haugsand <[EMAIL PROTECTED]>
Subject: Re: A challenge for you !
Date: 02 May 1999 23:36:56 +0200
* [EMAIL PROTECTED]
> [1 <text/plain; us-ascii (7bit)>]
> This is a simple version of an encryption program im making. 35 people
> have tried it, no one has cracked it. Give it a go and see if you can!
> Please email me if you do try to decrypt it.
I think you had a posting mistake. I found your above challenge and I
found some cipher text, but I could not find the algorithm. Just post
the algorithm and some will look at it.
--
Jon Haugsand
Norsk Regnesentral, <mailto:[EMAIL PROTECTED]> <http://www.nr.no/>
Tlf: 22852608/22852500, Fax: 22697660, Pb 114 Blindern, 0314 OSLO
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Factoring breakthrough?
Date: Sun, 2 May 1999 22:14:54 GMT
Terje Mathisen <[EMAIL PROTECTED]> wrote:
>> The way of sieving that everyone has been using for 10 or 15 years
>> doesn't take cache effects into account at all. As the speed of chips
>> continues to increase faster than the latency of main memory, a
>> cache-friendly method is bound to become more widespread eventually!
>
>Actually Rob, this has already happened, AFAIK.
>
>My own toy sieve code uses just 128 KB of table space, reusing the same
>block for each new area to be searched.
He's not talking about Erastosthenes' sieve ;-).
------------------------------
From: [EMAIL PROTECTED] (Virgil)
Crossposted-To: sci.math,comp.programming,de.org.ccc
Subject: Re: Hot new algorithm?
Date: Sun, 02 May 1999 17:47:51 -0600
In article <7gidob$enc$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>Numbersplit
>
>This is a method to split up big numbers into factors taking
>advantage of the 3rd binomic formula: (a-b)*(a+b)=a²+b²
Don't you mean (a+b)*(a-b) = a^2 - b^2 ?
--
Virgil
[EMAIL PROTECTED]
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Hot new algorithm?
Date: Mon, 03 May 1999 00:31:12 GMT
In article <7gidob$enc$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>This is from a friend of mine. I think it's worth reading.
>
>This is a method to split up big numbers into factors taking
>advantage of the 3rd binomic formula: (a-b)*(a+b)=a²+b²
You mean a²-b² of course...
[snip]
>Please give me a feedback if you know something about this method, if it's
>already known or really new or if you have improvements.
It's not that bad a method -- your friend is only 356 years too late. It was
originally discovered by Pierre de Fermat, and is called (coincidentally
enough) Fermat's method.
And, yes, if the factors are close together, this can be very effective.
However, for 512 bit composite numbers, the factors are almost never close
enough for this to be practical (and, the factors are typically chosen so
they are not too close, in order to frustrate this particular algorithm).
--
poncho
------------------------------
** 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
******************************
