Cryptography-Digest Digest #492, Volume #9 Mon, 3 May 99 02:13:03 EDT
Contents:
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
([EMAIL PROTECTED])
Re: Stream Ciphers and Quantum Computer Resistance ([EMAIL PROTECTED])
Re: Hot new algorithm? (Miguel A. Lerma)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: RSA-Myth (Jim Felling)
Neat stuff to see ([EMAIL PROTECTED])
Re: Hot new algorithm? (pete)
Re: How to Save MAGENTA
Re: Hot new algorithm? ("Ross Crawford")
Re: Predicting calculator pseudo-random numbers ("Franzen")
Cool Shadow: UNIX crypt(3) toy! (Logic)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Mon, 03 May 1999 00:56:03 GMT
Terry Ritter wrote:
> John Savard wrote:
>
> >[EMAIL PROTECTED] wrote, in part:
> >
> >>I'm talking about Ritter's suggestion in which the protocol
> >>chooses one of about 1000 ciphers at random for each message.
> >>It's not enough to include strong ciphers in the pool.
> >
> >No, it certainly wouldn't be.
[...]
> I have several times proposed and justified a multifaceted "fix
> package" to improve ciphering as we now know it. Here is the
> background; at the end I discuss "many cipher" system tradeoffs.
Obviously we know the background. You've noted the boring
repetition of assertions on both sides of the argument, but
his particular sub-thread is about an argument that is, I
believe, new.
Specifically: use of a per message choice from a pool of
many ciphers does not prevent catastrophic failure in the
event that one or a few of the ciphers fall. In real-world
enterprises and projects, the same information is carried by
many messages. Partitioning the messages fails to partition
the intelligence value of the traffic. Failure of a small
portion of the ciphers gives away a large part of the
intelligence.
Granted, multiple encryption protects a message if any of the
chained ciphers resists cryptanalysis. I think there are
reasonable arguments for and against multiple encryption, and
personally I'm on the against side. I think dynamically
choosing ciphers from a large pool is simply naive.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Stream Ciphers and Quantum Computer Resistance
Date: 3 May 1999 02:50:33 GMT
Reply-To: [EMAIL PROTECTED]
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> writes:
> Actually if one wants quantum computer resistance one should not be
>so worried about reversiblity.
Your ignorance is astonishing. Reversibility is very important since
there is a space trade-off in making an irreversible algorithm reversible.
This space trade-off could dramatically increase the number of quantum
bits and gates necessary to impliment an algorithm on a quantum computer
and could thereby hinder the ability to crack an algorithm on a
quantum computer.
> But one should worry more about the
>overall entropy of the system. If one is limited by using a weak method
>such as any of the AES canditates likely to be blessed by the NSA and
>if one is sending ascii messaages of a few dozen characters or more
>then quantum computers will be able to solve for the likely unique
>solution.
Oh really? Give us a proof.
>There are really two pratical ways to solve this problem
>one is to use a true OTP ( One Time PAd) and the other is to use an
>extremly high entropy system such as scott19u.zip where one uses a long
>random file of ones choice and than a password to protect it. But even
>then to be safe one should every so often change the long random key
>file since if both the source code and long secrect key file is stolen
>a quantum compter could be used to guess what password was used but it
>is many orders of magnitude safer than any of the AES candidate types
>with there small NSA friendly type of key lengths. But the trick is
>to have the entropy high enough such that more than one solution exists
>that way a quantum computer could never settle down on the correct
>solution.
Quantum computers do not "settle down" on the correct solution. And I'm
not aware of an analysis of an extension of the quantum search algorithm
to the case where there is more than one solution -- if you have one and
it shows that it dramatically decreases the effectiveness of the quantum
search algorithm, then I suggest that you post your reference.
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: [EMAIL PROTECTED] (Miguel A. Lerma)
Crossposted-To: sci.math,comp.programming,de.org.ccc
Subject: Re: Hot new algorithm?
Date: 3 May 1999 00:55:59 GMT
[EMAIL PROTECTED] wrote:
: This is a method to split up big numbers into factors taking
: advantage of the 3rd binomic formula: (a-b)*(a+b)=a�+b�
[...]
That is Fermat's method. Look for instance at
http://diamond.idbsu.edu/~marion/teaching/math306/306FermatmethodF98.htm
Miguel A. Lerma
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Mon, 03 May 1999 03:40:10 GMT
On Mon, 03 May 1999 00:56:03 GMT, in
<7gis72$prn$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] wrote:
>[...]
>Specifically: use of a per message choice from a pool of
>many ciphers does not prevent catastrophic failure in the
>event that one or a few of the ciphers fall. In real-world
>enterprises and projects, the same information is carried by
>many messages. Partitioning the messages fails to partition
>the intelligence value of the traffic. Failure of a small
>portion of the ciphers gives away a large part of the
>intelligence.
Compartmentalization is in fact in use by organizations which keep
secrets. It is hardly an unusual approach. The only thing unusual in
automatic random compartmentalization is the way information is
partitioned.
As far as I know, security "compartments" are normally organized by
"need to know" knowledge; essentially, one general secret per
compartment. In contrast, automatic compartmentalization would place
each message (or so) in the separate compartment of a different random
cipher. This is a vast increase in the number of "compartments." If
users confine themselves to one piece of information per message (not
continually recounting the past), this would seem to be superior to
normal security compartmentalization.
The argument that automatic compartmentalization is useless parallels
the argument that cryptography itself is useless, and is similarly
meaningless: Since users do disclose secrets, and cryptography cannot
enforce this, so cryptography must be useless; and with automatic
compartmentalization, since users do put a range of data in a message,
if that message is exposed, all the information is exposed, so
compartmentalization must be useless. But cryptography and
compartmentalization are tools, not solutions: advantages accrue when
the tools are used properly. To the extent that an entire history is
*not* recounted in each message, compartmentalization is always
superior to having no compartmentalization: For, without
compartmentalization, our entire history of past messages -- plus all
future messages -- may be exposed by one break.
>Granted, multiple encryption protects a message if any of the
>chained ciphers resists cryptanalysis. I think there are
>reasonable arguments for and against multiple encryption, and
>personally I'm on the against side. I think dynamically
>choosing ciphers from a large pool is simply naive.
But the question is whether you have a factual basis for this opinion,
and whether you draw your conclusions from a reasoned argument. None
of that is given here.
The argument against having many ciphers presumably rests upon the
supposed "strength" of the single cipher we would use instead. But we
have no factual basis for such opinion: At its best, cryptanalysis
can only provide an upper bound for strength, so the possibility of
successful unknown attack always exists. And if we use any single
cipher exclusively, *all* our data -- past *and* future -- may be
vulnerable to the failure of that one cipher.
But if we multi-cipher, any particular cipher we think strong can be
one stage of every randomly-constructed cipher-set we agree to use.
Such a system carries all the strength of the single-cipher solution,
with the added strength of other ciphers, new compartmentalization,
new easy cipher change if we get new cryptanalytic results, and also
imposes great new costs on the opposition. What is there to not like?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: RSA-Myth
Date: Mon, 26 Apr 1999 12:07:41 -0500
Matthias Bruestle wrote:
> Mahlzeit
>
> Jim Felling ([EMAIL PROTECTED]) wrote:
> > [EMAIL PROTECTED] wrote:
>
> > > The low is: how much time is needed to generate
> > > quasi primes used for business RSA encryption, the same order
> > > of time using same algorithms is needed for RSA modulus
> > > decomposition.
>
> > False. I can generate/evaluate candidate primes much faster than I can
> > factor numbers. There are many tests to determine if a number is prime
> > that do not rely on factoring that number.
>
> Even if you would have to factor the numbers it is not correct.
> When the modulus has the length n you only have to factor two
> numbers with length n/2 which is much easier.
I did not speak sufficiently clearly. My meaning was as follows. Given we are
using RSA with two primes p and q. [EMAIL PROTECTED] wrote that finding p
and q was equivalent in difficulty to primality testing candidate primes in that
area. This is wrong. Factoring is a much more difficult problem than primality
testing. Primality testing is a much simpler and more time efficient process than
factoring -- by a huge margin. That was all I was trying to say.
>
>
> Mahlzeit
>
> endergone Zwiebeltuete
>
> --
> PGP: SIG:C379A331 ENC:F47FA83D I LOVE MY PDP-11/34A, M70 and MicroVAXII!
> --
> 'If you want a picture of the future, imagine a boot stamping on a human
> face - forever. And remember that it is forever' (Orwell, 1984)
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.econ,sci.environment,sci.geo
Subject: Neat stuff to see
Date: Mon, 03 May 1999 04:52:19 GMT
Check out out this site if you are interested
http://www.geocities.com/Hollywood/Agency/8089/
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: pete <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.programming,de.org.ccc
Subject: Re: Hot new algorithm?
Date: Mon, 03 May 1999 00:12:19 -0400
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
>
> 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
It's a little bit buggy.
I'm using 32 bit unsigned longs.
Enter a big number 12345677
Solution found :29*425713=12345677
Enter a big number 12345679
Solution found :37*333667=12345679
but
Enter a big number 12345678
No solution found after 6172839 tests.
--
pete
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: How to Save MAGENTA
Date: 3 May 99 04:59:45 GMT
[EMAIL PROTECTED] wrote:
: The basic unit of that f-function, repeated many times, is a
: transformation involving two bytes, where each byte is replaced by itself
: XOR the S-box entry indexed by the original value of the other byte. This
: basic unit is non-invertible.
Oops, I think I got that backwards. However, it does not affect my point.
John Savard
------------------------------
From: "Ross Crawford" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.programming
Subject: Re: Hot new algorithm?
Date: Mon, 3 May 1999 15:31:34 +1000
Pete,
Read the algo again. It specifies z, a, b must be ODD numbers.
Regards,
ROSCO
pete <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> It's a little bit buggy.
>
> I'm using 32 bit unsigned longs.
>
> Enter a big number 12345677
> Solution found :29*425713=12345677
>
> Enter a big number 12345679
> Solution found :37*333667=12345679
>
> but
> Enter a big number 12345678
> No solution found after 6172839 tests.
> --
> pete
------------------------------
From: "Franzen" <[EMAIL PROTECTED]>
Subject: Re: Predicting calculator pseudo-random numbers
Date: Sun, 2 May 1999 22:59:33 -0500
Nathan Kennedy <[EMAIL PROTECTED]> wrote Thu, April 29, 1999 at 4:08 AM:
Geoff Lane wrote:
>>This is a curious question but I suspect the experts are here rather than
>>in any maths newsgroups.
>>
>>Suppose you have a pocket calculator with a "random" button. From a
limited,
>>sequential list of generated numbers is it possible to determine the
>>algorithm used and hence predict the sequence from any given point?
>>
>>I suspect that most calculators either use very poor "folk" algorithms or
>>standard algorithms described by Knuth or Numerical Recipes so the search
>>space may be quite limited.
>I posted about this a while ago and got no response. My guess was that the
>numbers generated by graphing calculators (generally a real between 0 and 1
>with maybe 6 or 9 digits of precision) were generated by a primitive PRNG,
>like the one in BASIC. I guessed (or maybe, hoped) that the ones in
>scientific calculators (between 0 and 1, only three digits) was based on
>button timings and thus truly random.
>
>I use a Casio fx-120 pocket scientific calculator for most stuff, it's
>handy. I wanted to know if it would be good for generating keys and OTPs
>or not.
I cannot find an fx-120 Casio. The Casio web site does not list that model.
Maybe it is out of production. I finally got an CFX-9850G out of curiosity.
Generic step one: Turn on your calculator and generate a single "random"
number. In my case, the number is 0.6813412629. Optional: Multiply this
number by ((2^31)-1), and by ((2^31)-2). See if either result is a whole
number. In my case the first result is 1,463,169,220. Now turn off your
calculator.
Generic step two: Turn your calculator back on and generate another single
"random" number. In my case this second number is different from the first.
It is 0.5193177124. I then multiply by ((2^31)-1) and get 1,115,226,295.
After all this hard work, what can I say about my results?
1. My calculator at least reseeds itself. The most primitive RNG's will
restart with the same "random" number each time you turn their calculator
off and on again.
2. The algorithm underlying this particular RNG is specifically the Lehmer
linear congruential formulation [((Seed * Multiplier) + Increment) mod 2^31
= Next Seed]. Each seed is transformed into a "random" decimal number by
being divided by ((2^31)-1).
I agree with Geoff Lane's general assertion. Simple Lehmer RNG's
predominate among calculators and computer programs at this time. TI & HP
calculators use more complex versions of the Lehmer RNG, as well as MS's
Excel spreadsheet. All are very deterministic, not particularly uniformly
random, and cannot be expected to stand up to supercomputer analysis.
---
Douglas McLean
------------------------------
From: [EMAIL PROTECTED] (Logic)
Subject: Cool Shadow: UNIX crypt(3) toy!
Date: 3 May 1999 00:55:16 -0500
Tired of easy-to-remember passwords and garbage-looking crypt(3) strings?
Now you can have it the other way around! Cool Shadow is a toy I wrote a
few weeks ago for all you UNIX/crypto-heads with too much time and CPU on
your hands. It generates random-ish passwords which encrypt to
cool-looking strings when run through crypt(3) for your passwd/shadow
file. Impress your friends! Scare the script kiddies who run crack
against your passwd file!
Pick it up at http://homepage.oz-online.net/~logic/coolshadow/
Of course it's free. Who would pay for such nonsense?
------------------------------
** 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
******************************
