Cryptography-Digest Digest #451, Volume #11 Thu, 30 Mar 00 20:13:01 EST
Contents:
Examples of topology related to crypto ? ([EMAIL PROTECTED])
Re: RNG based on primitive multiplicative generator. (lordcow77)
Re: Looking for some help on RSA public key/private key generation ("Joseph Ashwood")
Re: NIST publishes AES3 papers (Gregory G Rose)
Re: Help decrypt message exercise (Jim Gillogly)
Re: Looking for some help on RSA public key/private key generation (Paul Rubin)
Re: Q: Entropy (Bryan Olson)
Re: Examples of topology related to crypto ? (David A Molnar)
Re: Crypto Webpages (David A Molnar)
Re: Is it really NSA ?! ([EMAIL PROTECTED])
Re: Is it really NSA ?! ([EMAIL PROTECTED])
Re: OAP-L3: Semester 1 / Class #1 All are invited. ([EMAIL PROTECTED])
Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
([EMAIL PROTECTED])
Re: Factoring? (Scott Contini)
Re: Particular integer factors (Bob Silverman)
Re: Looking for some help on RSA public key/private key generation (Bob Silverman)
Re: Looking for some help on RSA public key/private key generation (David A Molnar)
Re: Looking for some help on RSA public key/private key generation (Bob Silverman)
Re: Particular integer factors (Scott Contini)
Re: Particular integer factors (JCA)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Examples of topology related to crypto ?
Date: Thu, 30 Mar 2000 23:19:27 GMT
Just out of curiosity, I am interested in
examples of how topology (topo) might relate
to cryptology. Here are two examples but if
you can think of more and have the time would
you please post them to this thread or send
them to my email. Thanks.
1) A few years ago, Michael Freedman (a
mathematician who won the Fields medal for
work in topo) made a suggestion which
inspired me to invent the idea, at least
independently, of trying to use topo to address
computability. More specifically, I was
attempting to use one- point
compactification, etc. to introduce the
concept of limits into complexity theory for
problems like P/NP. I never made any
significant progress but, IMHO, Freedman has
by applying topo to the theory of quantum
computation. For instance, his work implies
that topo quantum field theories (TQFTs) could
be used to create new quantum algorithms.
Quantum algorithms, such as Shor's, could be
very important for cryptanalysis. Here's two
of Freedman's relevant papers:
http://arxiv.org/abs/quant-ph/0001071
http://arxiv.org/abs/quant-ph/0003128
2) A few weeks ago in sci.crypt, Tim Tyler
started the thread "Cellular Automata (CA)
based public key cryptography". For this
purpose, one wants reversable CA. Topo is
very important in the theory of symbolic
dynamical systems and this theory is tied into
the question of reversability in CA- (symbolic
dynamics can be an application of automata
theory, or vice versa).
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: RNG based on primitive multiplicative generator.
From: lordcow77 <[EMAIL PROTECTED]>
Date: Thu, 30 Mar 2000 15:32:43 -0800
How are you defining a dot product between two integers? Over
the Euclidian space R^1, a dot product just reduces to a
multiplication, which doesn't make much sense. I think you mean
a mask of some sort.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Looking for some help on RSA public key/private key generation
Date: Thu, 30 Mar 2000 15:32:57 -0000
> >Yes, but by using a large e, the size of your d
decreases.
>
> Whaaaaaaat? No, d is the size of the modulus and
supposedly
> unpredictable.
No, length(d)+length(e) should be very close to
length(modulus), as in within 1
>
>
> >It depends on what will be done most often, if encryption
> >will be done distributed, but decryption is limited to 1
> >computer, d needs to be as small as possible. If
encryption
> >is central and decryption is distributed than e should be
> >small as is typical. Many of the environments I deal
with,
> >the number of messages is very large, and the decryption
and
> >encryption need to both take about the same amount of
time,
> >so by increasing the value of e it moves that way.
>
> Small d => easier to guess. In RSA, encryption is
inherently
> faster than decryption. Anyway, generating a small d from
> a known e is not an easy thing at all.
Yes a smaller d will be easier to guess, but with the sizes
involved, the difficulty is not decreased significantly so
I'm not overly worried. It is simply a matter of trading off
client speed and server speed, unless you go to severe
values the consideration of which is stronger is not a big
issue. Also it has been established that small values for e
are weak, by increasing e we increase the resistance against
some attacks, I put a limit of sqrt(sqrt(n)) for the maximum
value of e which limits the maximum erosion of the
protection of d. I, of course, always recommend going with
what you trust, as I said in another thread different people
trust different algorithms/sizes, some trust 3DES above
anything else, some people insist that it is weak (based on
imagined weaknesses).
Encryption is NOT inherently faster than decryption, the
speed is determined by the values for e and d. By choosing a
d and e of the same length, the timing will be virtually
identical. Instead it is generally used in a way that d
>>>>> e making it so that decryption takes much longer than
encryption. The observed speed differences are solely an
artifact of the chosen e and d.
Joe
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: NIST publishes AES3 papers
Date: 30 Mar 2000 15:39:11 -0800
In article <[EMAIL PROTECTED]>, John Myre <[EMAIL PROTECTED]> wrote:
>Derek Bell wrote:
>Note that two AES submissions (DEAL and Serpent) tried to build on
>DES to create a cipher matching NIST's requirements; and Serpent is
>still in there, as one of the five finalists.
True, but Serpent originally built on the DES
S-boxes (not the whole structure), and then they
changed the S-Boxes.
In other words, there is precious little of DES
left in Serpent. Nevertheless, I like it.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Help decrypt message exercise
Date: Thu, 30 Mar 2000 23:44:32 +0000
[EMAIL PROTECTED] wrote:
> williams Stallings' (cryptography and network security)
> exercises. I am stalled in exercise 2.4 that gives you
> Any help would be appreciated,
> 53��+305))6*;4826)4�.)4�);806*;48+8�60))85;;]8*;:�*8+83
> (88)5*+;46(;88*96*?;8)*�(;485);5*+2:*�(;4956*2(5*-4)8�8*
> ;4069285);)6+8)4��;1(�9;48081;8:8�1;48+85;4)485+528806*81
> (�9;48;(88;4(�?34;48)4�;161;:188;�?;
> and here is the frequency table (that I did)
> SYMBOL QT
> 8 34
Besides individual letter frequencies, go through and underline
repeated strings. In this case the symbol 8 is indeed an E, and
the word THE appears here and there, as you would expect in
English. Try each of the likely 3-letter repeats for THE and
see if anything recognizable pops out.
--
Jim Gillogly
9 Astron S.R. 2000, 23:42
12.19.7.1.9, 7 Muluc 17 Cumku, Second Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Looking for some help on RSA public key/private key generation
Date: 30 Mar 2000 23:55:09 GMT
In article <#ll$PBqm$GA.225@cpmsnbbsa05>,
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
>No, length(d)+length(e) should be very close to
>length(modulus), as in within 1
I don't get it and would like to see an example, of a reasonable sized
modulus N = pq, along with exponents d and e which are each about half the
length of N, with de==1 mod phi(N). Given N, how do you compute d and e
to have those properties?
>Encryption is NOT inherently faster than decryption, the
>speed is determined by the values for e and d. By choosing a
>d and e of the same length, the timing will be virtually
>identical. Instead it is generally used in a way that d
>>>>>> e making it so that decryption takes much longer than
>encryption. The observed speed differences are solely an
>artifact of the chosen e and d.
Yes of course you are correct, you can choose a large e so that e and
d are about the same size and that gives up the speed advantage of a
small e, but it doesn't make decryption any faster. What I don't see
is how to get a small d.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Thu, 30 Mar 2000 23:51:11 GMT
Mok-Kong Shen wrote:
> Given an arbitrary (finite) bit sequence, how does one actually
> go about in practice to determine the entropy it contains?
Remember that entropy is defined by probability. Given
a finite bit sequence but not a probability space,
there is no such thing as the entropy of the sequence.
> Are there concrete and dependable (accurate, exact) algorithms?
Well, there's the definition:
entropy of x, in bits = - log_base_2(probability(x))
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Examples of topology related to crypto ?
Date: 30 Mar 2000 23:52:03 GMT
In sci.crypt [EMAIL PROTECTED] wrote:
> Just out of curiosity, I am interested in
> examples of how topology (topo) might relate
> to cryptology. Here are two examples but if
> you can think of more and have the time would
> you please post them to this thread or send
> them to my email. Thanks.
It's not exactly cryptography, but Nir Shavit has a paper
on using topology to reason about what kinds of protocols can
run on various kinds of asynchronous architectures :
G. Hoest and N. Shavit. Towards a Topological Characterization of
Asynchronous Complexity, Proceedings of
the 16th Annual ACM Symposium on Principals of Distributed
Computing (PODC), Santa Barbara (1997),
pages 199-208.
http://www.math.tau.ac.il/~shanir/publications/HS-complexity.ps
It's also in Vol. 1000 of Springer-Verlag LNCS (which is where I found
it), as part of a "topics in computer science" collection of papers.
I don't pretend to understand the result, unfortunately.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Crypto Webpages
Date: 30 Mar 2000 23:53:08 GMT
RecilS <swehmeier @ mindspring> wrote:
> Just a URL and a short description would be great
My personal web page is
http://www.hcs.harvard.edu/~dmolnar/
It has some cryptographic content. Mostly unfinished pages on various
things which (used to) interest me.
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is it really NSA ?!
Date: Thu, 30 Mar 2000 23:59:57 GMT
In article <[EMAIL PROTECTED]>
,
Arthur Dardia <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>
> Hmm...attacking the NSA? Definitely an interesting fantasy...
>
> However, to do it properly, I wouldn't suggest an electronic attack, but
> more of a physical, armed-to-the-teeth attack. First things first,
> don't bother cutting power - I'm positive they have a generator, and
> once their generator kicks in, I'm sure they'd be suspicious. Secondly,
> I'm sure they have metal detectors...porcelain guns? I know I saw them
> in some movie. :)
>
The russians built a device that can shoot
an electromagnetic pulse and tested it in an
open desert- like area. It stopped dead a
running car by blowing out its electronics
from a large distance away (I don't remember
how far). The U.S. and probably other countries
have these devices. On TV (maybe it was the
Discovery Channel) there was a guy who built
a smaller one of these using commonly
available parts.
I do *not* recommend this: but it
*might* be possible to use such a device to
clandestinely cause electrical disruptions in
Ft. Meade from a distance. I wouldn't be
surprised if they could detect such an assault
and, anyways, their critical sytems are
underground for good reason.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is it really NSA ?!
Date: Fri, 31 Mar 2000 00:02:45 GMT
In article <[EMAIL PROTECTED]>
,
Arthur Dardia <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>
> Hmm...attacking the NSA? Definitely an interesting fantasy...
>
> However, to do it properly, I wouldn't suggest an electronic attack, but
> more of a physical, armed-to-the-teeth attack. First things first,
> don't bother cutting power - I'm positive they have a generator, and
> once their generator kicks in, I'm sure they'd be suspicious. Secondly,
> I'm sure they have metal detectors...porcelain guns? I know I saw them
> in some movie. :)
>
The russians built a device that can shoot
an electromagnetic pulse and tested it in an
open desert- like area. It stopped dead a
running car by blowing out its electronics
from a large distance away (I don't remember
how far). The U.S. and probably other countries
have these devices. On TV (maybe it was the
Discovery Channel) there was a physicist or
electrical engineer who built a smaller one of
these using commonly available parts
(although he wouldn't say how on TV).
I do *not* recommend this: but it
*might* be possible to use such a device to
clandestinely cause electrical disruptions in
Ft. Meade from a distance. I wouldn't be
surprised if they could detect such an assault
and, anyways, their critical sytems are
underground for good reason.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited.
Date: Fri, 31 Mar 2000 01:13:04 +0100
Just passing through this NG, but reading the post's about the PRNG in
OAP-L3 I just couldn't help remembering the discussions about Zvi
Netiv's AV software in alt.comp.virus. Perhaps Anthony Stephen Szopa
and Zvi Netiv should compare notes :o)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Sunday People 26/3/2000: "FORGET YOUR PASSWORD... END UP IN JAIL"
Date: Fri, 31 Mar 2000 01:17:45 +0100
On Wed, 29 Mar 2000 23:41:38 +0300, "Stormshadow"
<[EMAIL PROTECTED]> wrote:
>
>"PJS" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> But, on the other hand, when a dead person last made Home Secretary?
>Never. But if one is killed, there will be others..
>
>> Is that what you want, 'cos that's what'll 'appen?!
>> Straw is a man of profoundly anti-democratic instincts, I and say that
>> killing him would be morally justifiable, considering the damage he will do,
>> and I'm not a person normally given to advocating such extreme measures.
>I'm not making a stance on the moral justification of killing, I'm just saying
>that such extreme measures would be useless. There are other, cleaner methods
>of persuasion.
Tactical nuclear strike of Parliament during the Queens speech ?
Roll over Guy Fawkes :o)
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Factoring?
Date: 31 Mar 2000 00:28:46 GMT
In article <[EMAIL PROTECTED]>,
proton <[EMAIL PROTECTED]> wrote:
>
>Is there any point in deveolping methods to factor numbers
>with small factors?
>
>Or is the game plan all about factoring large numbers with
>two large factors only?
>
>/proton
Algorithms that are quick for finding small prime factors are often
useful as subprocedures to algorithms like NFS and MPQS, since
the multiple large prime variations require quickly finding
small factors. Often the Shanks square forms method is used, but
other possibilities are Pollard-rho and elliptic curve method.
Scott
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Particular integer factors
Date: Fri, 31 Mar 2000 00:17:11 GMT
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
>
> When attempting to factorize a (large) integer does it help to know
> that it is
> the product of two unknown factors whose sizes are known?
>
Only if one of them is small enough to be accessible to ECM
>
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Looking for some help on RSA public key/private key generation
Date: Fri, 31 Mar 2000 00:20:40 GMT
In article <0UOE4.95572$[EMAIL PROTECTED]>,
"Tom St Denis" <[EMAIL PROTECTED]> wrote:
> Why do people say phi(N) when in your own paper you suggest to use lcm(p -
> 1, q - 1)?
Both work. LCM(p-1, q-1) will be slightly smaller.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Looking for some help on RSA public key/private key generation
Date: 31 Mar 2000 00:13:05 GMT
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> Yes a smaller d will be easier to guess, but with the sizes
> involved, the difficulty is not decreased significantly so
> I'm not overly worried. It is simply a matter of trading off
How small is your d in terms of N ?
Have you looked at :
Cryptanalysis of RSA with private key d less than N^0.292
Authors: D. Boneh and G. Durfee
Abstract:
We show that if the private exponent d used in the RSA system is less than
N^0.292 then the system is insecure. This is
the first improvement of an old result of Wiener showing that
when d < N^0.25 RSA is insecure. We hope our approach
can be used to eventually improve the bound to d < N^0.5.
Reference:
In Proceedings Eurocrypt '99, Lecture Notes in Computer Science,
Vol. 1592, Springer-Verlag, pp. 1--11, 1999.
URL :
http://crypto.stanford.edu/~dabo/abstracts/lowRSAexp.html
>From what I can tell by skimming through the paper, the attack requires
only access to the public key N and e. This is in contrast to another
recent attack in the same spirit ("Factoring N = p^r q for large
r," Boneh, Durfee, and Howgarave-Graham CRYPTO '99), which is really
impressive until you notice the minor fact that you need to know (or
guess) the top 20 or so bits of the factor p.
Anyway, assuming that all you need is the public key in order to
mount this attack, it seems worth looking at.
Thanks,
-David
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Looking for some help on RSA public key/private key generation
Date: Fri, 31 Mar 2000 00:25:24 GMT
In article <epE1JKpm$GA.258@cpmsnbbsa05>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> Because the lcm() version delivers a d that is of smaller
> size (possibly by a significant amount),
It better not be smaller by a *significant* amount. This, of course,
depends on what you mean by significant.
and this delivers
> much faster decryption. This is also part of the reason that
> when I spec RSA I recommend using random e of up to sqrt of
> the size of pq (or N in common notation).
Huh? this last point is irrelevant!
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Crossposted-To: sci.math
Subject: Re: Particular integer factors
Date: 31 Mar 2000 00:41:08 GMT
In article <[EMAIL PROTECTED]>,
JCA <[EMAIL PROTECTED]> wrote:
>
> When attempting to factorize a (large) integer does it help to know
>that it is
>the product of two unknown factors whose sizes are known?
>
>
>
It sure does... If you know the size of the factors is small enough, you
may choose to use the elliptic curve method rather than the number field
sieve or mpqs. It is a bit frustrating to use a general purpose factorisation
algorithm on a huge number and then to find that it has a small prime
factor which could've been discovered had you put a little more time into your
elliptic curve factorisation attempts.
Scott
------------------------------
From: JCA <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Particular integer factors
Date: Thu, 30 Mar 2000 16:53:43 -0800
[EMAIL PROTECTED] wrote:
> In sci.crypt JCA <[EMAIL PROTECTED]> wrote:
> > When attempting to factorize a (large) integer does it help to know
> > that it is
> > the product of two unknown factors whose sizes are known?
>
> Well, it lets you skip a primality test and searching for small
> factors. :) I doubt it helps significatly though, apart from simply
> letting you jump right to mpqs or nfs.
Yes, that's what I was aiming at: Can the sophisticated methods used
to factorize large integers make anything out of the extra piece of
information about the factors mentioned above? More tentatively, could
a new, highly performant method be developed that exploits that knowledge?
------------------------------
** 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
******************************
