Cryptography-Digest Digest #733, Volume #11 Mon, 8 May 00 14:13:01 EDT
Contents:
Re: Factoring vs. Discrete Log Problem (DLP) (David A. Wagner)
Re: Crypto Export (Jeffrey Williams)
Re: Factoring vs. Discrete Log Problem (DLP) ("Scott Fluhrer")
Re: Hardware RNG (Terry Ritter)
Re: Tempest Attacks with EMF Radiation (Diet NSA)
Re: Tempest Attacks with EMF Radiation (Diet NSA)
Re: cryptographically secure (Paul Koning)
Re: Why no civilian GPS anti-spoofing? / proposal (Paul Koning)
Re: Sample Output from SBOXGEN (Mike Rosing)
Re: Factoring vs. Discrete Log Problem (DLP) (Roger Schlafly)
Re: Newbie question about primes (Anton Stiglic)
Re: distributed RSA? (Anton Stiglic)
Re: An argument for multiple AES winners (Anton Stiglic)
Re: quantum crypto breakthru? (Mike Rosing)
Re: Factoring vs. Discrete Log Problem (DLP) (Bob Silverman)
Re: Hardware RNG (Mike Rosing)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Factoring vs. Discrete Log Problem (DLP)
Date: 8 May 2000 08:30:39 -0700
In article <[EMAIL PROTECTED]>, Roger <[EMAIL PROTECTED]> wrote:
> The largest successful factoring was to a
> 512-bit RSA modulus. The largest DLP solution so far is 283 bits,
> as reported in EuroCrypt '98. The factoring used a whole lot
> more computer time, but no one is claiming yet that it is
> feasible to do a 512-bit DLP on today's hardware.
Actually, Odlyzko writes that taking discrete logs mod a prime p
and factoring a RSA-composite n appear to have roughly comparable
complexity when using today's best algorithms and when p and n have the
same length. It is not known whether this feature of today's algorithms
is a coincidence or not.
I'm no discrete log expert, but based on those comments from Odlyzko,
I'd have to guess that 512-bit DLP's may well be within reach of today's
architecture.
I would not read too much into factoring & discrete log "records".
It seems that the factoring problem is slightly 'sexier' and thus receives
more attempts at setting a record.
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: Crypto Export
Date: Mon, 08 May 2000 11:12:04 -0500
Well, it makes a small amount of sense. On the surface.
But consider multinational company X. Builds a product using strong, public
algorithm Z in the US. Then has it's subsidiary in country A build a similar
product using the same algorithm (note that exporting the algorithm is not
illegal, just executable software). The foreign product is built by non-US
citizens outside the US. But the encrypted output of one of the products can
be decrypted by the other (and vice versa).
So much for export controls.
Most of the arguments which are similar to the one Adam raised seem to
rely on the assumption that no one but an American is capable of turning an
algorithm into software. Assinine, if not insulting.
Adam Durana wrote:
> > I don't think you will find any arguments which make any sense (I've never
> seen
> > a sensible argument for it).
>
> Actually there is a sensible argument and you have most likely heard it, but
> you didn't like it. As long as the US puts limits on the export of
> technologies that use strong cryptographic algorithms there is no way some
> sort of basic communications standard will evolve that incorporates strong
> crypto. Sure you might say there are already many standards that involve
> strong crypto, but there is still a great deal of communications that go on
> around the world that don't use strong crypto or any encryption at all.
> From the standpoint of the agencies, such as the NSA and CIA, that monitor
> communications around the world, this situation is ideal. Now if there was
> no limits on the export of crypto, eventually every method of communication
> would be encrypted in some form. And this would make those agencies' job's
> a lot harder.
>
> I'm sure you've heard this claim before, and it does make sense. I am not
> saying its good or bad, but it does make sense.
>
> - Adam
--
Jeff Williams
Software Design Engineer
DNA Enterprise, Inc
1240 E Campbell Rd, Richardson, TX, 75081
972 671 1972 x265
[EMAIL PROTECTED]
Did you know that there is enough sand in
north Africa to cover the entire Sahara?
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Factoring vs. Discrete Log Problem (DLP)
Date: Mon, 8 May 2000 09:00:05 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Eric Hambuch wrote:
> >
> > Tom St Denis wrote:
> > >
> > > Martin Hamann wrote:
> > > >
> > > > Is it true that figuring out how to factor integers efficiently will
also
> > > > make it easier to solve the DLP. In other words, are the two
problems that
> > > > closely related ? Will a 'solution' to the factoring problem, also
wreck all
> > > > systems based on DLP ?
> > > >
> > > > Any thoughts ?
> > >
> > > You have it backwards, any solution to the DLP can be used in the IFP,
> > > not the opposite.
> >
> > Do you have a proof ? (I've been looking for this, but couldn't find
> > anything)
>
> Actually no I just take it as folklore. I am sure it has been shown
> though... Keep a heads up, maybe one of the IFP pro's will respond.
It's known that if you can solve the DLP for a composite modulus, you can
factor that modulus. You can do that by using the DLP oracle to do square
roots.
What I don't know is whether, if you have an oracle that can solve the DLP
for prime moduli, whether that will help you factor.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Hardware RNG
Date: Mon, 08 May 2000 16:14:05 GMT
On Mon, 08 May 2000 00:49:23 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt Richard Parker
<[EMAIL PROTECTED]> wrote:
>"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>> I currently have an application that could make use of some
>> hardware number generation. I was wondering if someone could
>> point me to some online resources for designs for the fool
>> things.
>
>Will Ware describes his design for a hardware RNG at the following URL:
>
> Hardware Random Bit Generator
> <http://world.std.com/~wware/hw-rng.html>
I am not happy about using digital logic in analog mode, nor the use
of synchronous logic for asynchronous sampling. (A failure to observe
digital set-up and hold times generally affects balance.)
In contrast, I don't have a finished design, but I do have some
preliminary 5 volt designs which produce analog noise suitable for
sampling with a sound card. Most of these depend upon a synthesized
low-voltage "zener" having a specified noise signal which is then
amplified. The next step would be to provide software to read the
sound card noise input when needed; if anybody can provide help with
that I would be grateful.
Of particular interest is an extensive statistical, FFT and
autocorrelation characterization on the resulting noise, revealing
significant faults in various designs. Personally, I think the
autocorrelation results were by far the most revealing, and that is
something I have not seen done before.
http://www.io.com/~ritter/NOISE/NOISCHAR.HTM
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Subject: Re: Tempest Attacks with EMF Radiation
From: Diet NSA <[EMAIL PROTECTED]>
Date: Mon, 08 May 2000 09:14:44 -0700
In article <
8f6ked$n0a$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Richard Herring)
wrote:
>Diet NSA wrote in message
<[EMAIL PROTECTED]>...
>>If the snake-oil salesman are more
>>correct than you are (in the context this
>>thread is discussing), then why not accept
>>their correct use of the terminology?
>
>They are not "more correct", since nothing in my usage is
incorrect.
>It may be that they are no longer incorrect. The government
webpages
>you cite show that "EMF" is acquiring a new meaning, in the
usual
>way of linguistic change;
The thread was referring to the phrase
"EMF radiation" (which is conventionally
understood to mean "electromagnetic
field radiation"), and not just the phrase
"EMF". Often "EMF" stands for
electromotive force which is a correct
usage.
"If we do not prevent highly classified secrets from being stolen,
then how are we going to sell them to the Chinese?"
- Madeleine Albright (addressing recent thefts)
========================================================================
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Tempest Attacks with EMF Radiation
From: Diet NSA <[EMAIL PROTECTED]>
Date: Mon, 08 May 2000 09:30:14 -0700
In article <
8f6j84$n0a$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Richard Herring)
wrote:
>As indeed do I - meaning a far-field, propagating solution.
>I still think it's not helpful, and may be a source of
confusion,
>to apply it to other forms of field. It can also be a suggestion
>that one doesn't properly understand the correct usage - which
>is why I wouldn't use it in the way the snake-oil salesmen do.
>
Although "EMF radiation" conventionally
means "electromagnetic field radiation",
your distintion is valid and more accurate
even if not commonly made. The exposure
to low frequency EM fields should occur
mainly in the near field region, and the
term "radiation" should be reserved for
the far field region.
"If we do not prevent highly classified secrets from being stolen,
then how are we going to sell them to the Chinese?"
- Madeleine Albright (addressing recent thefts)
========================================================================
* 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: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: cryptographically secure
Date: Mon, 08 May 2000 12:09:56 -0400
Ali Tofigh wrote:
>
> Hi!
>
> I'm in urgent need for a cryptographically secure random number
> generator... I'm studying cryptography and implementing an RSA-system
> and therefore I need a random number generator that can generate
> large numbers. Around 400-500 bits long at least.
Two suggestions:
1. Read RFC 1750.
2. Find the device driver for /dev/random in the Linux sources and
read that. (drivers/char/random.c if I remember right). Examine
whether it does the things that RFC 1750 recommends. If you can
answer that you are well on the way to knowing what you need to
know for this task.
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Lucent Corporation, 50 Nagog Park, Acton, MA 01720, USA
! phone: +1 978 263 0060 ext 115, fax: +1 978 263 8386
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "A system of licensing and registration is the perfect device to deny
! gun ownership to the bourgeoisie."
! -- Vladimir Ilyich Lenin
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Crossposted-To: sci.geo.satellite-nav
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
Date: Mon, 08 May 2000 12:34:18 -0400
Paul Rubin wrote:
> ...
> The civilian signal on the other hand is unencrypted and has no anti-spoofing.
>
> This actually scares me, now that a multi-carrier civilian system (L5
> etc.) has been announced, and airliner navigation will depend on it.
> One can imagine a terrorist action sending slightly spoofed GPS
> signals that cause two planes to crash into each other. ...
> I'd like to propose that civilian signals on the new carriers have
> public-key digital signatures, signed by the satellites. Receivers
> would be able to check the signatures by having the public key inside.
I'm not sure this would help. Remember that GPS involves
the solution of equations in 4 unknowns, one of which is time.
So one spoofing approach is to do a replay attack with a well
chosen delay (namely the desired offset divided by the speed
of light). So I don't see how signing the signal will be
of any help at all. And the usual anti-replay mechanisms
don't seem to apply here, either.
At one time the proposals for the use of GPS in precision
navigation (i.e., instrument landing, as opposed to enroute
nav) were required to include real-time monitoring of signal
integrity and very quick reporting of faults. That is more
likely to help (but still subject to the problem of attack with
directional antennas).
Crosschecking with other means of navigation also helps,
assuming they don't both get spoofed at the same time. But
the rules talk about the use of GPS (or whatever else) as
a sole source of navigational data. That's hardly new;
an ILS approach uses the ILS, it doesn't crosscheck in real
time with an ADF or the like.
paul
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Sample Output from SBOXGEN
Date: Mon, 08 May 2000 11:24:07 -0500
Tom St Denis wrote:
>
> Mike Rosing wrote:
> >
> > Tom St Denis wrote:
> > > ln2 = size of output in bits
> > > S = 0
> > > for x = 0 to n-1
> > > for y = 0 to log2(n)
> > > S += HT[f(x) xor f(x xor (1<<y))];
> > >
> > > And expect S to be around nlog2(n)(ln2/2), nlog2(n) = number of
> > > itterations, (ln2/2) = half the bits change...?
> >
> > That's a basic brute force method, I'd expect S to be a factor of 2
> > too big since you loop over every possible x. But it should give
> > the right statistics otherwise.
>
> Yes it actually is twice as big as it should, how would I change it?
Notice in the above code that x runs from 0 to n-1. when x = 9 and y =
0,
you xor f(9) with f(8). This is the same as when you xor f(8) with
f(9),
so you've done each term twice.
It would be a major pain to make the code efficient. I'd just divide by
2 and not worry about it :-)
If you want to take the painful route, build a table of pairs and then
step thru the table. Building the table will be slow, but you only do
it once for each n, m combination. The first entries might be (0, 1)
(0, 2) (0, 4) ... (0, 2^log2(n)) (1,1), (1,2), ... (2,2) (2,4) ... (3,1)
(3,2) ...
A simpler way might be to just build all pairs, then go thru and
eliminate
duplicates by brute force.
Have fun!
Patience, persistence, truth,
Dr. mike
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Factoring vs. Discrete Log Problem (DLP)
Date: Mon, 08 May 2000 10:21:25 -0700
"David A. Wagner" wrote:
> Actually, Odlyzko writes that taking discrete logs mod a prime p
> and factoring a RSA-composite n appear to have roughly comparable
> complexity when using today's best algorithms and when p and n have the
> same length. It is not known whether this feature of today's algorithms
> is a coincidence or not.
>
> I'm no discrete log expert, but based on those comments from Odlyzko,
> I'd have to guess that 512-bit DLP's may well be within reach of today's
> architecture.
Odlyzko is just looking at the sieving phase, IIRC. It is phase 2 that
is
much harder for DLP. Apparently there is some dispute about how
important
phase 2 will be for larger key sizes. Here is what Bob Silverman says.
(But read the paper for arguments that phase 2 is more difficult than
others think.)
>From Bob Silverman:
The General Number Field Sieve (GNFS or just NFS) is a general purpose
algorithm for either factoring large integers or for solving an ordinary
discrete logarithm problem. Its run time depends only on the size of the
number being factored, or the size of the underlying field for the
discrete logarithm problem. It is the fastest method known today and has
two phases. In the first phase, a sieving operation requiring moderately
large amounts of memory is conducted on independent computers. This
phase is used to construct a set of equations. In the second phase a
large Cray with massive memory has then been used to solve this set of
equations. Once a solution has been found to this set of equations
factoring the number or solving the discrete log takes a miniscule
amount of time and memory.
The amount of time it takes to factor a number of x bits is
asymptotically the same as the time it takes to solve a discrete log
over a field of size x bits. However in practice solving discrete log
problems has been more difficult than factoring equivalent numbers.
While there are several reasons for this, the main reason is that
solving the matrix for a discrete log must be done using multi-precision
integer arithmetic while the matrix for factoring is solved mod 2 and
thus one can use simple bit operations. It has been estimated that for
large x, one can break a discrete log of size x-30 in about the same
time as factoring an x-bit number. Throughout this paper we shall assume
that solving the two problems are equivalent under NFS and henceforth
shall only discuss factoring.
http://www.rsalabs.com/bulletins/bulletin13.html
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Newbie question about primes
Date: Mon, 08 May 2000 13:27:27 -0400
"Earl K. Nimoy" wrote:
> "JoeC" <[EMAIL PROTECTED]> wrote:
>
> >As I understand it, one of the key factors(pardon the pun) in the security
> >of PGP and similar is the time taken to factor a large prime number.
>
> It's impossible to factor a prime number. By definition, the only factors a
> prime number has are itself and 1.
On the opposite, it's trivial. The prime factorization of a prime p is
*trivial*,
it is simply p = p.
:)
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: distributed RSA?
Date: Mon, 08 May 2000 13:36:01 -0400
Mark Wooding wrote:
> I thought that distributed RSA was something rather different, actually
> done using cunning secret-sharing systems and so on.
>
Yes indeed. The commonly used definition of distributed RSA involves
a scheme that uses a secret key shared among N players in a way that
t < N players (but no less) can join together and use the RSA function
(encryption with the private key, of signature with the private key).
The strong point of such a scheme is that the private key is not stored as
a whole on one single machine. An attacker would need to break into t
machines
in order to be able to re-construct the private key. t-1 shares of the
private key gives you zero knowledge about the private key.
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: An argument for multiple AES winners
Date: Mon, 08 May 2000 13:41:40 -0400
==============2BED88907E6F16B126F212FA
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Mok-Kong Shen wrote:
> <...>
>
> It just occurs to me that the same applies in
> respect of hidden patent claims. If there are e.g.
> three AES winners, the chance of all of them have
> hidden patent claims is likely to be fairly small.
>
> <...>
This point has been misunderstood by many.
You are calculating the probability in the wrong way.
It's not an *and*, but an *or*. If you have 3 algos,
with probability of p1 that the first will have a component
that is patented, p2 for the second and p3 for the last,
the probability that the whole has a component that is
patented is p1 + p2 + p3, which is >= to any single pi.
This comes from the fact that you are reliable for what
you have done in the past (if you used a patented
algorithm in the past, they can sue you).
The more algos you use, the greater the risk of having
a patent attack.
Anton
==============2BED88907E6F16B126F212FA
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>
Mok-Kong Shen wrote:
<blockquote TYPE=CITE><...>
<p>It just occurs to me that the same applies in
<br>respect of hidden patent claims. If there are e.g.
<br>three AES winners, the chance of all of them have
<br>hidden patent claims is likely to be fairly small.
<p><a href="http://home.t-online.de/home/mok-kong.shen"><...></a></blockquote>
This point has been misunderstood by many.
<p>You are calculating the probability in the wrong way.
<br>It's not an *and*, but an *or*. If you have 3 algos,
<br>with probability of p1 that the first will have a component
<br>that is patented, p2 for the second and p3 for the last,
<br>the probability that the whole has a component that is
<br>patented is p1 + p2 + p3, which is >= to any single pi.
<p>This comes from the fact that you are reliable for what
<br>you have done in the past (if you used a patented
<br>algorithm in the past, they can sue you).
<p>The more algos you use, the greater the risk of having
<br>a patent attack.
<p>Anton</html>
==============2BED88907E6F16B126F212FA==
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: quantum crypto breakthru?
Date: Mon, 08 May 2000 11:35:52 -0500
Roger wrote:
>
> Actually, the implementations can leak bits because of
> physical errors. For some current work, see:
> http://www.quantum.univie.ac.at/research/crypto/
That's due to the way they generate the correlated photons, there
may be duplicates in the same coherence time. Change the method
and you can eliminate the leak. But it's a real system, so maybe
there's no way to eliminate that leak. I think the leak rate is
too high at 10^-7, but for their test it's pretty small.
Thanks for the pointer.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Factoring vs. Discrete Log Problem (DLP)
Date: Mon, 08 May 2000 17:49:10 GMT
In article <8f6miv$jil$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> In article <[EMAIL PROTECTED]>, Roger <[EMAIL PROTECTED]> wrote:
> > The largest successful factoring was to a
> > 512-bit RSA modulus. The largest DLP solution so far is 283 bits,
> > as reported in EuroCrypt '98. The factoring used a whole lot
> > more computer time, but no one is claiming yet that it is
> > feasible to do a 512-bit DLP on today's hardware.
>
> Actually, Odlyzko writes that taking discrete logs mod a prime p
> and factoring a RSA-composite n appear to have roughly comparable
> complexity when using today's best algorithms and when p and n have
the
> same length. It is not known whether this feature of today's
algorithms
> is a coincidence or not.
>
> I'm no discrete log expert, but based on those comments from Odlyzko,
> I'd have to guess that 512-bit DLP's may well be within reach of
today's
> architecture.
This is problematic. The sieving has been done to solve a DL
problem over GF(2^509). [work by McCurley et. al.]
But the matrix has not been solved.
Whereas the matrix for RSA-512 took 10 days on a Cray C90, it was
solved over GF(2). Solving the matrix for GF(2^509) requires
working mod 2^509-1. I would not hazard a guess as to how long
this will take. If one uses the CRT and solves the matrix modulo
some small primes p_i such that product(p_i) > 2^509-1, this would
require solving the matrix at least 16 separate times if one wants the
primes to remain single precision. And one must still work mod p_i,
rather than mod 2. At a "rough" guess, it is probably several
hundred times harder to solve the matrix as it was for RSA-512.
What makes solving DL problems harder than factoring, using NFS, is
the near-impossibility of solving the matix, even for fields around
500 bits.
--
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: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Hardware RNG
Date: Mon, 08 May 2000 12:00:45 -0500
Joseph Ashwood wrote:
>
> I need the actual designs (or a standard interface, like I
> said in the other half of this thread, I'll build
> conversions as needed), I can't be limited to just a couple
> of motherboards.
Check out my design (www.terracom.net/~eresrch under /dev/random).
You can change the noise source to any analog noise you like, the
basic design is mathematically sound. Probably could build a lot
of 'em pretty cheap too.
Patience, persistence, truth,
Dr. mike
------------------------------
** 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
******************************
