Cryptography-Digest Digest #507, Volume #9 Thu, 6 May 99 11:13:03 EDT
Contents:
Re: Shamir's TWINKLE Factoring Machine (Damian Weber)
Re: Some thoughts on Diffusion (wtshaw)
Recommended RSA lengths (was: Re: Shamir's Discover) (Peter L. Montgomery)
Re: Roulettes (Mok-Kong Shen)
Re: Roulettes (Mok-Kong Shen)
Re: Roulettes ("Lassi Hippeläinen")
Re: Shamir's TWINKLE Factoring Machine (Damian Weber)
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Random permutation (Mok-Kong Shen)
Re: Roulettes (Mok-Kong Shen)
Re: Roulettes (Terje Mathisen)
Re: Discrete Logarithm Question (Emmanuel BRESSON)
Re: The simplest to understand and as secure as it gets. ([EMAIL PROTECTED])
Re: Obvious flaws in cipher design (Lincoln Yeoh)
Re: Commercial PGP for Linux? (Bernie Cosell)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Damian Weber)
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: 6 May 1999 11:27:23 GMT
In article <7gqe2g$b5k$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] writes:
>
> Thanks for the info, btw where could someone (maybe I :) ) find info on the
> details of factoring a RSA number or a Discrete log?
In the ASIACRYPT'96 proceedings you'll find the RSA-130
factorization.
In the CRYPTO'98 proceedings you'll find the solution
of McCurley's DL-challenge.
-- Damian
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Some thoughts on Diffusion
Date: Thu, 06 May 1999 05:19:14 -0600
In article <[EMAIL PROTECTED]>, Piso Mojado <[EMAIL PROTECTED]> wrote:
> Malcolm Herring wrote:
> >
> > Surely diffusion says nothing at all about the security of an algorithm.
>
> Block ciphers are not provably secure, but they all have diffusion.
My GVA does not have it; as a block cipher, according to my broad
definition, it does not need it.
> If you would belittle diffusion, what would you propose as a trait
> that says something about security?
That's easy: that you can't hack the ciphertext at all, known text attacks
don't work as the algorithm fails to cooperate. Of course, this creature
of mine is really strange according to popular prejudices.
>
....
>
> One can create bad ciphers easily. All of the good ones have diffusion.
The common strategies so popular for the *good ones* group them ready for
a common means of breaking.
> I have heard your kind of comments before, but they are not
> persuasive. All 15 AES candidates have diffusion. If someone
> made an AES candidate without diffusion, it would be rejected
> immediately. It is a requirement. It is so basic that sophisticated
> people want it to be called trivial and unimportant, but they
> are mistaken. Conservative ciphers have more diffusion then ones
> which emphasize speed to excess.
Diffusion can be added to any cipher, but if not necessary, why bother?
No, to prove to me that diffusion is important, you should be able to
easily attack a cipher that does not use it. Here's is guessing that you
won't try. You could not succeed anyway if I made the choice of cipher.
>
> Sophisticated people such as yourself would overlook the
> requirement for diffusion, and look to Authority to fail to
> break the cipher. Thinking designers, provide diffusion with
> emphasis on plenty of diffusion, as well as other traits.
Ah, the surface details, how superficial! The only measure of valid
measure of security is resistance to recovering the key. As the world of
slight-security crypto continues to crumble, remember there is an
alternative effective technology. Too bad that it is so simple to
understand; and so difficult to envision attacking at all.
And, you need to think quantum leaps ahead to deliver yourself from all
the mudfights over marginal increases in security.
--
What's HOT: Honesty, Openness, Truth
What's Not: FUD--fear, uncertainty, doubt
------------------------------
From: [EMAIL PROTECTED] (Peter L. Montgomery)
Subject: Recommended RSA lengths (was: Re: Shamir's Discover)
Date: Wed, 5 May 1999 07:46:45 GMT
In article <7gnsm8$316$[EMAIL PROTECTED]>
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> writes:
> I wonder if any one has been smart enough to see how rapidly
>RSA key lengths have been increasing over the last few year to
>be safe. All one gets to read about is that key lenght of X can
>be found in Y time but keys of X+N are safe till the sun burns
>out. But it seems that new methods are found every year so it
>seems reasonable that newer methods will be found in just a few short
>years but the articles just replace the old X+N with a new value
>for X and never mention a few years ago it was safe forever.
>Are there any plots based on this kind of projection.
I was one of 16 participants at a July, 1991, workshop on
Public-Key Cryptography sponsored by E.I.S.S.
(European Institute for System Security). Our report appears in
Th. Beth, M. Frisch, G.J. Simmons (Eds.)
Public-Key Cryptography: State of the Art and Future Directions,
Lecture Notes in Computer Sciences, 578,
Springer-Verlag, 1991.
Page 81 of this report says
For the most applications a modulus size of 1024 bit
for RSA should achieve a sufficient level for ``tactical''
secrets for the next ten years. This is for long-term
secrecy purposes, for short-term authenticity purposes
512 Bit might suffice in this century.
Page 39 of that report estimates 500,000 MIPS-years
to factor a general 512-bit integer via ppmpqs.
The number field sieve was rather new in 1991 (it had been
used to factor 2^512 + 1 but some thought it impractical
for general numbers). Nonetheless page 44 of the report warns
Thus is it not unlikely that the number field sieve is better
than the ppmpqs for factoring integers in the 512-bit range.
The 1991 recommendation for 1024-bit keys is still valid in 1999.
The report makes no recommendation for key lengths next century.
The recent RSA-140 factorization and Shamir's announcement are
warnings that 512-bit keys are vulnerable in 1999, although they
are probably OK for `short-term authenticity purposes'.
--
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Roulettes
Date: Thu, 06 May 1999 14:01:53 +0200
Paul Rubin wrote:
>
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >Boris Kazak wrote:
> >>
> >
> >> Just use octahedric dice (8faces) and get your random numbers in octal.
> >
> >Are such dices on sale? BTW, maybe Rubik's cube (there is also a
> >4*4*4 variant) and similar toys could be of use.
>
> Yes, go to a game store and you can get N-sided dice for
> various N including N=4, 6, 8, 10, 12, 20, etc.
> Of course N=6 is the easiest to find. N != 6 is mostly
> used for role playing games like Dungeons and Dragons.
But according to mathematics there exist exactly 5 regular polyhedra:
tetrahedron, hexahedron, octahedron, dodecahedron and icosahedron.
I think also that it is difficult to read out from a octahedron,
i.e. which face it is to take when such a dice lies on the table.
I suppose it may be good to use the icosahedron with its 20 faces to
generate random numbers in [0, 15]. One simply uses 16 arbitrarily
selected faces and marks the rest as irrelevant.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Roulettes
Date: Thu, 06 May 1999 10:06:52 +0200
Boris Kazak wrote:
>
> Just use octahedric dice (8faces) and get your random numbers in octal.
Are such dices on sale? BTW, maybe Rubik's cube (there is also a
4*4*4 variant) and similar toys could be of use.
M. K. Shen
------------------------------
From: "Lassi Hippeläinen" <[EMAIL PROTECTED]>
Subject: Re: Roulettes
Date: Thu, 06 May 1999 14:55:28 +0300
Paul Rubin wrote:
> In article <[EMAIL PROTECTED]>,
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >Boris Kazak wrote:
> >>
> >
> >> Just use octahedric dice (8faces) and get your random numbers in octal.
> >
> >Are such dices on sale? BTW, maybe Rubik's cube (there is also a
> >4*4*4 variant) and similar toys could be of use.
>
> Yes, go to a game store and you can get N-sided dice for
> various N including N=4, 6, 8, 10, 12, 20, etc.
> Of course N=6 is the easiest to find. N != 6 is mostly
> used for role playing games like Dungeons and Dragons.
My pal working in the next room has various dices, and also a crystal ball and
a magick wand on his table. But he doesn't play games, he is a project manager.
He has to make work estimates and time schedules.
BTW, the number of his room is 666. Must be a random coincidence.
-- Lassi
------------------------------
From: [EMAIL PROTECTED] (Damian Weber)
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: 6 May 1999 11:17:09 GMT
>[EMAIL PROTECTED] (Bruce Schneier) writes:
>>
>>Could there be mathematical advances which make the matrix problem for
>>the discrete-log problem equivalent to the factoring one?
>
> I don't think so. For RSA, you can solve the linear equations in mod
> 2. For discrete log systems, you have to work modulo the
> characteristic of the field.
Not modulo the characteristic of the field but modulo the order
of the multiplicative group of the finite field. This then reduces
to prime factors of that order which, when considering finite fields
of degree>=3, may well be greater than the characteristic.
This is why the matrix step in DL is likely to be harder than the one
in factoring.
-- Damian
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 06 May 1999 12:28:34 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 06 May 1999 04:14:20 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
> 3) We observe the actual output and find that it does
> not have those statistical characteristics.
You did not take enough samples to make that determination. Claiming
that you took 20,000 single bit samples is fallacious. In reality you
took just one sample.
If you measure the speed of light with one sample consisting of
20,000 individual waves of the EM field, you cannot claim to have
taken 20,000 samples of one wave.
You need to look into the "estimation of error in samples", which can
be quite large for just one sample.
Bob Knauer
"There is much to be said in favour of modern journalism. By giving us the opinions
of the uneducated, it keeps us in touch with the ignorance of the community."
-- Oscar Wilde
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Random permutation
Date: Thu, 06 May 1999 14:47:47 +0200
A problem raised in another thread is whether it is possible e.g.
to generate a random permutation of [0, 15], given only a random
generator for [0, 15] and no generator for [0, 14], etc. One way I
can think of is quite trivial: One obtains successive outputs from
the generator and discards duplicates until one gets 16 numbers.
Question: Are there more efficient ways of achieving the same goal?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Roulettes
Date: Thu, 06 May 1999 15:06:01 +0200
Patrick Juola wrote:
>
> But there are lots of other dice out there that are symmetrical,
> but not regular, polyhedra. For example, to construct a fair
> 10-sided die, simply construct a regular pentagon and place two
> vertices a fixed distance "above" and "below" the center of the
> pentagon. Connect all vertices and you have a solid with the
> necessary 10-fold symmetry, even though the faces are not themselves
> symmetric.
You are right. One the otherhand to do the same for a dice with
16 faces wouldn't be very nice I suppose.
M. K. Shen
------------------------------
From: Terje Mathisen <[EMAIL PROTECTED]>
Subject: Re: Roulettes
Date: Thu, 06 May 1999 15:00:51 +0200
Mok-Kong Shen wrote:
>
> Paul Rubin wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >Boris Kazak wrote:
> > >>
> > >
> > >> Just use octahedric dice (8faces) and get your random numbers in octal.
> > >
> > >Are such dices on sale? BTW, maybe Rubik's cube (there is also a
> > >4*4*4 variant) and similar toys could be of use.
> >
> > Yes, go to a game store and you can get N-sided dice for
> > various N including N=4, 6, 8, 10, 12, 20, etc.
> > Of course N=6 is the easiest to find. N != 6 is mostly
> > used for role playing games like Dungeons and Dragons.
>
> But according to mathematics there exist exactly 5 regular polyhedra:
> tetrahedron, hexahedron, octahedron, dodecahedron and icosahedron.
>
> I think also that it is difficult to read out from a octahedron,
> i.e. which face it is to take when such a dice lies on the table.
> I suppose it may be good to use the icosahedron with its 20 faces to
> generate random numbers in [0, 15]. One simply uses 16 arbitrarily
> selected faces and marks the rest as irrelevant.
This idea can just as easily be applied with any random source and any
desired random range [0..N-1].
I.e. if you have a two-sided dice (i.e. a coin) you can get 0 or 1.
As soon as you have enough bits B (2^B >= N) you can get a number, by
using the current value if in range, discarding it and trying again if
not.
If you want random numbers in the [0..9] range you'll have to make 4
throws of the coin, and you'll have a 7/16 chance of having to discard
the result, so on average you'll have to try nearly twice for each
result.
You can however get arbitrarily close to zero discard ratio by combining
a bunch of random results in a single block:
9^1 = 9 -> 2^4 = 16 0.4375
9^2 = 81 -> 2^7 = 128 0.3672
9^3 = 729 -> 2^10 = 1024 0.2881
9^4 = 6561 -> 2^13 = 8192 0.1991
9^5 = 59049 -> 2^16 = 65536 0.0990
So if you make 16 throws of the coin, you have less than 10% chance of
having to discard the results, and you get 5 random numbers out of the
process.
Including the discarded sets, you'll average about 3.5 throws/number.
The next big improvement on this occurs with 73 throws giving 23
numbers, for a ratio of 3.1739, and a 0.1257% chance of having to
discard.
The limit value would be the binary log of the range, i.e. about
3.169925 throws/number.
The same principle can easily be applied with M-sided dice.
Terje
--
- <[EMAIL PROTECTED]>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
------------------------------
Date: Thu, 06 May 1999 09:13:11 -0400
From: Emmanuel BRESSON <[EMAIL PROTECTED]>
Subject: Re: Discrete Logarithm Question
Vedat Hallac wrote:
> The problem came up from something along the lines of the proof you have
> posted (a more primitive version, you might say). If N = p*q, with p and q
> prime, and Phi(N) > p+q,
> then for any 0<a<N,
> a^(N+1) == a^(p+q) ( mod N )
>
> If Phi(N) < p+q,
I do not think tis case occurs frequently, since phi(N)=(p-1)(q-1)= n-q-p+1,
you should have phi(N)>p+q almost everytime...
Bye,
Emmanuel
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto,alt.privacy
Subject: Re: The simplest to understand and as secure as it gets.
Date: Thu, 06 May 1999 13:50:19 GMT
> > Original Absolute Privacy - Level3 Version 4.0 Windows GUI - SHAREWARE
> >
> > http://www.ciphile.com
> >
> >
>
> Actually I think scott19u.zip is stronger.
> Get it free executable and source code visit my site.
Really? Prove it.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Lincoln Yeoh)
Subject: Re: Obvious flaws in cipher design
Date: Thu, 06 May 1999 14:55:59 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 1 May 1999 12:32:36 +0200, [EMAIL PROTECTED] (Jaime
Suarez) wrote:
>On Wed, 28 Apr 1999 00:12:41
>GMT, SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
>>
>>> Any password or passphrase used should have adequate
>>> size, should not be stored or transmitted unencrypted, and
>>> should be hashed before use.
>>>
>>
>> Actually Hashing is a bad idea since it usually reduces
>>the size of the effective key.
>>
>
>Could you explain this more? If users passwords are a few characters long and
>I hash them to 128 or 160 bits, why am I reducing the size of the effective
>key?
Given a good cryptographic hash there is a high probability that you
aren't.
Anyway what you should do is salt the passwords and hash em (possibly
recursively based on salt). That makes precalculated bruteforcing harder.
Based on my flawed intuition, hashing would make the bit distribution more
unpredictable, and if there are any flaws in the encryption algorithm, that
might make it harder to exploit.
For example if short passwords were just padded with nulls, you'd get keys
like
01000001010000100100001100000000000000000000 ... 0000000000
vs
01010111000110111011101111011010110000011101 ... 10100111010
Having everything predictable at one end is likely to make things easier in
event of a flaw.
Cheerio,
Link.
****************************
Reply to: @Spam to
lyeoh at @[EMAIL PROTECTED]
pop.jaring.my @
*******************************
------------------------------
From: [EMAIL PROTECTED] (Bernie Cosell)
Crossposted-To: comp.security.unix
Subject: Re: Commercial PGP for Linux?
Date: Thu, 06 May 1999 14:55:48 GMT
Jim Gillogly <[EMAIL PROTECTED]> wrote:
} Bernie Cosell wrote:
} > Well, just to close off this thread, I thought I'd mention that I called
} > NAI and discovered that a _one_year_, _single_server_ license for PGP for
} > Linux is *two*thousand*dollars*. Ouch!!
}
} Good heavens! That certainly doesn't close off the thread!
}
} Are they talking about a central server that handles enterprise PGP-ing
} for a very large company? Or is "server" in this case an individual
} Linux workstation? It surely can't be the latter unless they're trying
} to kill off the product.
I believe that the PGP package they quoted me was licensed to run on *one*
server. I don't know what sort of arrangements you can make if you need to
install it on a thousand workstations or something like that. [BTW: a two
year license was something like $3200 and a lifetime license was, I think,
$4500. But they did make it clear: "one server"]. Turns out that was what
I was worrying about and so that mostly closed *my* thread, but they were
friendly enough on the phone: perhaps one of you might want to inquire
about the licensing arrangements available for individuals/workstations
rather than "servers", per se.
Does make the GNU privacy package look a _lot_ better, no?? :o)
/bernie\
--
Bernie Cosell Fantasy Farm Fibers
[EMAIL PROTECTED] Pearisburg, VA
--> Too many people, too few sheep <--
------------------------------
** 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
******************************
