Cryptography-Digest Digest #289, Volume #9 Fri, 26 Mar 99 15:13:04 EST
Contents:
Re: RSA key distribution ([EMAIL PROTECTED])
Re: Factorising large numbers (Chris Monico)
Re: IDEA Encryption (Boris Kazak)
Re: Factorising large numbers ([EMAIL PROTECTED])
seeking your opinion: client authentication (denis bider)
Re: compare RSA and D-Hellman (Medical Electronics Lab)
Re: Random Walk (R. Knauer)
Re: a-8d~0.2844.5k:-89y ("hapticz")
Re: compare RSA and D-Hellman ([EMAIL PROTECTED])
Re: RSA key distribution (Paul Rubin)
Re: Assymetry cryptography is dead :)) (Francois Grieu)
Re: Factorising large numbers ("Tony T. Warnock")
Help with DSS Prime Number Generation (Matthew T Carter)
Re: Message Digest (wtshaw)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA key distribution
Date: Fri, 26 Mar 1999 16:30:51 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
> In article <7df9gn$655$[EMAIL PROTECTED]>,
> Roger Schlafly <[EMAIL PROTECTED]> wrote:
> >I don't know whether requiring strong primes is in RSADSI's business
> >interests or not. Either way, the issue is controversial.
>
> Let me guess. RSADSI has a patent on the method of generating these
> supposedly strong primes. So in order to follow the standard, you
> have to license from them. How convenient?
No. We have no patent on the method. It would be hard to patent such a
simple and obvious (to one skilled in the art) method. One can not patent
an algorithm in any case. One can only patent the application of said method.
I do not like to get involved business issues. Let me point out that
RSADSI has a lawsuit against Mr. Schaffly (as I understand it for patent
infringement) and he has some sort of suit against us, (the nature of which
I do not know).
I believe that in the past Mr. Schaffly wanted to sell his own crypto toolbox,
including the RSA Algorithm and (for business reasons I know nothing about, I
was not even employed by RSA at the time) RSA refused him a license.
He has also had an axe to grind against ANSI/NIST for some time as well. He
has repeatedly protested the inclusion of any patented method in any
standard.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Chris Monico)
Subject: Re: Factorising large numbers
Date: Fri, 26 Mar 99 06:54:43 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>Hi,
>
> This is my first time here. A while ago I had an idea for
>factorising large numbers which I haven't seen anyone mention
anywhere
>so I thought I'd run it past you all.
>
> The basic idea is as follows. Suppose we want to factorise 21.
>We can see that it ends with a 1 so we can deduce that the two
factors
>of it must end with either 1,1 (twice) 3,7 , 7,3 or 9,9(twice).
>That is, 6 combinations out of 100 so we can immediately throw away
>94% of the search space. This can then be carried on to the second
>from last digit and so on. I've implemented a version which converts
>the numbers to binary and works on them before converting the answers
>back because I think it gives me a slight edge over doing it in
>decimal.
>
>I can give anyone the code (C++) if they want it although its a bit
>messy and I've got a lot more ideas for optimising it which I haven't
>implemented yet. I tested it on MSVC5 as a console application and it
>works quite nicely. I've tested it on a few numbers and it seems to
>get better as the numbers get bigger. As an aside, does anyone have a
>large number (prime x prime) which I could test it on?
I think I've got a few lying around. Just so you know, ppmpqs can
factor the last one rather quickly.
250650431571687420754919
28156293808444714733245429
1722824766699254411375436109
131575204043896538318536055411
31053138633790577260357466956109
5976881552959214110853942044976983
290431855783161670043997121896713773
58393522999876394681333709135996185113
2245154900351667354482886738670269090871
61208352903158885563791676858099818993943
26829100170447402683126914881381308168434001
669445988283450797286250207356161655076618001
583512169543905377453911161823442291008580772623
23897407329502991178514659735262470118583718952109
2097943205368874149235050981944581716440028511491087
252264343781154125339651802990069682852165171409846893
50807560922188767334350965164015974887076049654019747069
8260119073841493644611906196067909917809410709497428678759
257176656795465810434077540662613560280772788573948560071017
52039413920525812941853253758461773765001901550220169245241309
414698450209116205348999557674647758563334810914720485620822113
258267129911592788705593846670189501087927864680776174250275044729
55121280038346853151657377737234769646874338355093481468779533560031
2726949722199801217917308392949498490245676889233342534007027021870283
2848266666657882138088202635341407416136163549539788256624917625979520
49
1976906308308721148904172393408366183595851544128831523256792628338752
2873
4251881609531360986275333030099528662033489976652667667719652063806877
24787
3381705951732581687583178687624680068877599955020519434905237153875420
24997881
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: IDEA Encryption
Date: Fri, 26 Mar 1999 09:24:45 -0500
Reply-To: [EMAIL PROTECTED]
Curious George wrote:
>
> Where can I find a source code of IDEA Encryption? Is IDEA the
> strongest encryption right now?
======================
Try < http://www.rpini.com > and browse their Crypto CD online.
May be you will end up ordering one for yourself, who knows...
The site is in Switzerland.
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Factorising large numbers
Date: Fri, 26 Mar 1999 16:20:59 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi,
>
> This is my first time here. A while ago I had an idea for
> factorising large numbers which I haven't seen anyone mention anywhere
> so I thought I'd run it past you all.
I mean no insult but have you actually LOOKED??
I do not know you personally. But I find too often that amateurs want to
'invent first', then check what has been done later. They can save themselves
much effort by a little library research before they start inventing.
>
> The basic idea is as follows. Suppose we want to factorise 21.
> We can see that it ends with a 1 so we can deduce that the two factors
> of it must end with either 1,1 (twice) 3,7 , 7,3 or 9,9(twice).
> That is, 6 combinations out of 100 so we can immediately throw away
> 94% of the search space.
Rest deleted...
The method is well known. It was known to Fermat/Legendre. It is known as
the use of exclusion moduli. See Knuth Vol 2 for a rather complete
discussion. The method is hopeless for anything much over 30 decimal digits.
It is a purely exponential algorithm.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (denis bider)
Subject: seeking your opinion: client authentication
Date: Fri, 26 Mar 1999 18:30:59 +0100
Hello folks,
with the help of Applied Cryptography and the X.509 standard, I have
devised an authentication technique for a specific application. However,
I'm not quite sure whether it's secure enough and I'd like to hear your
opinion about it.
The context is such: we have a server and a client, where an SSL session
between the server and the client is already established and all we have
to do is to authenticate the client. Because there's an SSL session going
on, we already have a secured channel and we trust the server's identity;
we only have to find out if the client really is who he claims to be.
The way I would perform the client authentication is this:
1. The client sends the server its name, C, and its certificate, A<<C>>:
--> C, A<<C>>
2. The server checks the validity of the client's certificate, then
generates some random data, rS, and sends it to the client:
<-- rS
3. The client generates some random data, rC. The client then computes a
hash of rS and rC combined and encrypts the hash with its private key.
The encrypted hash is
sent to the server along with rC:
--> rC, Cs[h(rS, rC)]
4. The server computes the hash of rS and rC, decrypts the hash it
received from the client and then compares the two hashes. If they match,
the client indeed represents who it claims to represent.
Do you find any obvious security gaps in the above protocol or is it OK
as it is?
denis bider
my email is: denis (at) zaslon.si
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: compare RSA and D-Hellman
Date: Fri, 26 Mar 1999 11:47:20 -0600
Sassa wrote:
>
> > See IEEE P1363.
>
> thank you.
>
> where can i find it on the net?
http://grouper.ieee.org/groups/1363/draft.html
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Fri, 26 Mar 1999 17:02:12 GMT
Reply-To: [EMAIL PROTECTED]
On 26 Mar 1999 09:05:57 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>>The problem is in accepting an unknown amount of uncertainty.
>That's where "expert judgement" comes in. In my "expert judgement,"
>I don't want that job and I won't take it.
This whole issue has a straightforward explanation - if people would
just catch on to the real meaning behind the concept of probability.
Probability for finite random sequence generation does not mean
absolute certainty, no matter how confident someone thinks it is.
Passing or failing statistical tests does not characterize a process
as random or non-random - it only gives an indication that it *might*
be random or non-random based on the notion of pseudorandomness.
Some of the confusion about probability theory comes from the looney
interpetations of quantum measurement. People may not realize that
Schrodinger invented his famous Cat to expose the insanity of the
Copenhagen interpretation. He knew perfectly well that it is crazy to
talk about his Cat being in a superposition of 1/2 alive and 1/2 dead,
before the measurement of its actual condition.
The correct interpretation of probability theory, which apparently has
some people agitated, is that statistical tests do not characterize a
process as random or non-random, any more than the Schrodinger wave
equation characterizes the actual condition of the Cat.
Statistical tests are useful only in tipping you off to the
*possibility* that a process is random or non-random, but that is all
they are good for - to give you a hint. All Schrodinger's equation
tells you is that the Cat *could* be alive or dead - it does not tell
you what the actual condition is. To determine the actual condition
for an actual Cat, you must do something else than look at statistical
measures of ensembles of Cats.
To decide conclusively whether a process is random or non-random
requires an analysis that is not statistical in nature - an analysis
based on first principles. Look upon your beloved statistical tests
only as a measure of a property of random number generation called
"pseudorandomness", and let that property serve as a guide in your
quest for processes that are truly random or non-random. But do not
let it blind you - deceive you into thinking that just because it says
it is highly confident, therefore it is absolutely certain.
As Williams & Clearwater state in their book on quantum computing:
"As we show, even when random number generators pass such statistical
tests, the sequence of numbers it generates may still not be random
enough to serve as an approximation to a true random process." That's
the statement of physicists, and shows you how they deal with true
randomness in quantum mechanics.
Pseudorandomness, which is measured with statistical tests, is neither
a necessary nor sufficient condition for true randomness - it is only
an approximation to true randomness, one which is not really all that
good even in the limit of large numbers.
One thing is for sure about a discussion of true randomness - it
exposes people's epistemological prejudices. The position I have
taken, for example, exposes my Realism worldview very clearly. Others
have the view that if it a process has the *appearance* of randomness
exposed by statistical tests - then it is close enough to be truly
random.
Close enough for government work, eh.
Bob Knauer
"Outside of the killings, Washington D.C. has one of the lowest
crime rates in the country".
-- Marion Barry, Mayor of Washington D.C.
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: a-8d~0.2844.5k:-89y
Date: Fri, 26 Mar 1999 11:57:38 -0500
hmmmmm, now thats a chilling idea!
--
best regards
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: compare RSA and D-Hellman
Date: Fri, 26 Mar 1999 17:54:43 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> hey, it seems you've rambled a bit,
>
> so, i'll type my question again:
May I suggest to everyone that they READ about this subject before discussing
it further? The RSA FAQ has a good discussion, as does the HAC or Schneier's
book.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: RSA key distribution
Date: Fri, 26 Mar 1999 17:34:02 GMT
In article <7dgcnr$vo6$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>> Let me guess. RSADSI has a patent on the method of generating these
>> supposedly strong primes. So in order to follow the standard, you
>> have to license from them. How convenient?
>
>No. We have no patent on the method. It would be hard to patent such a
>simple and obvious (to one skilled in the art) method.
This is good to hear, though the PTO has handed out many patents for
obvious methods in the past and continues to do so. The comp.compression
FAQ gives references to several different patents on the basic technique
of run length coding.
>One can not patent an algorithm in any case. One can only patent the
>application of said method.
Using the method to generate primes for use with RSA in a cryptography
system would count as an application.
>I do not like to get involved business issues. Let me point out that
>RSADSI has a lawsuit against Mr. Schaffly (as I understand it for patent
>infringement) and he has some sort of suit against us, (the nature of which
>I do not know).
The stuff on his web page is interesting reading; you might look at it.
------------------------------
From: [EMAIL PROTECTED] (Francois Grieu)
Subject: Re: Assymetry cryptography is dead :))
Date: Fri, 26 Mar 1999 19:51:49 +0100
"Arthur" <[EMAIL PROTECTED]> wrote :
> 4731083528105746283956593479028465928745473
41*3917285674659911261*29457203471209423131373
Francois
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Factorising large numbers
Date: Fri, 26 Mar 1999 12:35:26 -0700
Reply-To: [EMAIL PROTECTED]
Chris Monico wrote:> As an aside, does anyone have a
> >large number (prime x prime) which I could test it on?
>
> I think I've got a few lying around. Just so you know, ppmpqs can
> factor the last one rather quickly.
>
> 250650431571687420754919
> 28156293808444714733245429
> 1722824766699254411375436109
> 131575204043896538318536055411
> 31053138633790577260357466956109
> 5976881552959214110853942044976983
> 290431855783161670043997121896713773
> 58393522999876394681333709135996185113
> 2245154900351667354482886738670269090871
> 61208352903158885563791676858099818993943
> 26829100170447402683126914881381308168434001
> 669445988283450797286250207356161655076618001
> 583512169543905377453911161823442291008580772623
> 23897407329502991178514659735262470118583718952109
> 2097943205368874149235050981944581716440028511491087
> 252264343781154125339651802990069682852165171409846893
> 50807560922188767334350965164015974887076049654019747069
> 8260119073841493644611906196067909917809410709497428678759
> 257176656795465810434077540662613560280772788573948560071017
> 52039413920525812941853253758461773765001901550220169245241309
> 414698450209116205348999557674647758563334810914720485620822113
> 258267129911592788705593846670189501087927864680776174250275044729
> 55121280038346853151657377737234769646874338355093481468779533560031
> 2726949722199801217917308392949498490245676889233342534007027021870283
> 2848266666657882138088202635341407416136163549539788256624917625979520
> 49
> 1976906308308721148904172393408366183595851544128831523256792628338752
> 2873
> 4251881609531360986275333030099528662033489976652667667719652063806877
> 24787
> 3381705951732581687583178687624680068877599955020519434905237153875420
> 24997881
Nice, growing by about 100 each time. I tested my homegrown P-1 and rho
methods on the first two. The P-1 takes 59 and 90 seconds and rho takes
105 and 162 seconds. Fortran implementation on a 400mhz Pentinum-II. I
haven't done an elliptic curve yet. Will eventially do elliptic curve,
quadratic sieve and variants, the number field sieve. The last two need
really big memory for the matrix so they are not really suitable for a PC.
The quadratic sieve has inner loops on the sieving and matrix parts that
run in one clock (or 1/2 or 1/4 clock on newer machine) per step on the
vector machines. Just for fun I'll probably implement SQUFOF.
Tony
------------------------------
From: [EMAIL PROTECTED] (Matthew T Carter)
Subject: Help with DSS Prime Number Generation
Date: 26 Mar 1999 18:31:50 GMT
I'm working on implementing the prime number generator from the DSS
(FIPS-186-1) standard, and am having difficulty getting my data to match
the test patterns provided in the standard. I've been successfully able
to generate the same Q value as shown in the standard, but I can't get
the corresponding P value to match. Unfortunately, the standard does not
provide any intermediate results of the generation process, so I'm
struggling debugging the problem.
Does anyone have any intermediate values for V, W, X, and C for this
algorithm so that I can debug my implementation?
Note that I am using SHA-1, and the updated test patterns provided by
NIST in FIPS-180 change notice No. 1, 12/30/96.
Thanks in advance.
Carter
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Message Digest
Date: Fri, 26 Mar 1999 12:52:22 -0600
In article <fYvK2.248$[EMAIL PROTECTED]>, "karl malbrain"
<[EMAIL PROTECTED]> wrote:
>
> So, practically, the answer to your question is EXPECT a value of 1 digested
> value for 1 message. Karl M
If a fixed length Message Digest is considered too brief, consider that
any strong algorithm can produce a respectable signature simply by
processing with a specified key on plaintext, or ciphertext, provided that
the encryption key for the ciphertext was different.
Although more narrowly defined by some, such output might also fit in the
general definition of a MAC. It might be best to use a separate algorithm
for getting the MAC and for getting the ciphertext on which to make the
MAC from.
When we get into multiple algorithms, we run the risk of some sort of
unknown combination adding weakness, but aside from straight classical
interactions between ciphers, this is sure to be a rare problem best
addressed in original design of the ciphers.
--
Ethnic clensing does not appear to be a response to a high moral calling.
------------------------------
** 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
******************************
