Cryptography-Digest Digest #290, Volume #14 Fri, 4 May 01 02:13:01 EDT
Contents:
Re: RSA BRUTE FORCE ([EMAIL PROTECTED])
Re: Elementary Question on rsa (Kevin Henry)
Re: Elementary Question on rsa ("Tom St Denis")
Encryption Algorythm ("EE")
Re: _Roswell_ episode crypto puzzle -- THANK YOU! (billt)
TWInKLE (Kamran A Kashef)
Re: Encryption Algorythm ("Tom St Denis")
Re: A Question Regarding Backdoors (billt)
Re: A Question Regarding Backdoors ("Tom St Denis")
Re: GNFS source code? (jlcooke)
Re: Rijndael Galois Field construction problem. (jlcooke)
Re: GNFS source code? ("Tom St Denis")
Re: GCHQ Reorganization ? [Spoiler] (John Savard)
Re: GNFS source code? (Ben Smith)
Re: TWInKLE ("Peter L. Montgomery")
Re: How much math is required to study this? (Xcott Craver)
Re: Free Triple DES Source code is needed. (Bill Unruh)
Re: Free Triple DES Source code is needed. (Bill Unruh)
Re: Random and not random (Matthew Skala)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA BRUTE FORCE
Date: Fri, 04 May 2001 01:14:10 GMT
Erictim <[EMAIL PROTECTED]> wrote:
: i agree with you. thanks. but i assumed many of these possibilities could be
: cut out. if you multiply 6257 * 6356 you get 3976942. if you multiply
: 62574933 * 63560461 you get 3977291588524113.
: if N = 39772916239307209103. note that the 3977291 is the same. i still assume
: that as you go farther down along(with correct digits) P and Q that more and
: more digits along N would be exactly correct(is this wrong?). thus the pairs
: which produce the most correct digits would be tested and the rest dropped. so
: i guessed that it would be more like 40 blocks of 10 digit numbers than one
: giant pair of 300 digit numbers.
I think part of the question is, how did you arrive at 6257 and 6356? When you
chose 6 and 6 as the first digits, why did you rule out 13 and 3, 2 and 18
(the factors don't have to be the same length), 4 and 9 or 5 and 7? You would
have had to try all of these, you never know which one will yield the right
number. Your technique looks really good when you assume that you'll guess
the correct digit, but you really can't. When you try this yourself, start
with a big number, not with two factors. In fact, try it with reasonably
small numbers, like 12345.
Mark
--
Mark Wutka
------------------------------
From: Kevin Henry <[EMAIL PROTECTED]>
Subject: Re: Elementary Question on rsa
Date: Thu, 03 May 2001 20:24:48 -0400
Tom St Denis wrote:
>
> "Kris Reyes" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Hello, I'm just a freshman at college, I apologize for such an elementary
> > question.
> >
> > But in the rsa algorithm, where z = (p-1)(q-1), and you pick a number d
> > which is relatively prime to z, what exactly does relatively prime to z
> > mean??
>
> Means gcd(d, z) = 1, or they share no common prime factors.
>
> Tom
Which means no common factors at all, other than 1.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Elementary Question on rsa
Date: Fri, 04 May 2001 01:23:44 GMT
"Kevin Henry" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > "Kris Reyes" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > Hello, I'm just a freshman at college, I apologize for such an
elementary
> > > question.
> > >
> > > But in the rsa algorithm, where z = (p-1)(q-1), and you pick a number
d
> > > which is relatively prime to z, what exactly does relatively prime to
z
> > > mean??
> >
> > Means gcd(d, z) = 1, or they share no common prime factors.
> >
> > Tom
>
> Which means no common factors at all, other than 1.
Ah but really we only count prime powers i.e
30 is 2*3*5 not 6*5 or 10*3
Tom
------------------------------
From: "EE" <[EMAIL PROTECTED]>
Subject: Encryption Algorythm
Date: Thu, 3 May 2001 19:36:37 -0400
Is there a way to know if an encryption algorithm is secure? I would also
like to know how strong this algorithm is.
------------------------------
From: billt <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: _Roswell_ episode crypto puzzle -- THANK YOU!
Date: Fri, 04 May 2001 01:53:15 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> [EMAIL PROTECTED] (Timothy A. McDaniel) wrote:
>
> >I've not read either group before, and I'm not sure whether a
> >crossposting to rec.puzzles and sci.crypt is in order -- I saw only
> >one person doing it, and he, well, ... Please lambaste me if I have
> >violated the local mores.
> >
> >The latest (US) episode of the TV show Roswell ... oh, spoiler warning
> >had a character sign a credit card receipt with a string of 1s and 0s.
> >One person posted it as....
>
>
> This puzzle (with its million possible answers) prompts me to post THE
> RIGHT QUESTION which you should ask entities that claim to be visiting
> space aliens.
>
> Entity: G'day, we are from xxx xxx [distant civilisation]
> You: Please tell me the factors of F20 (2^1048576+1)
>
> A sufficiently advanced civilisation would be able to do this. We
> can't (at present)
>
> Steve
>
Wow! For years I have tried to cone up with THE RIGHT QUESTION, and armed
with only an engineering-level math background, could not.
Here's the scenario. Joe Sixpack (sorry for the stereotype) is transported
out of his doublewide, taken to the mother ship where he receives the usual
medical exam in a white room. He is given a small amount of information to
memorize and sent back to the trailerpark.
He has memorized something that can (and will) be written down on a 3x5 card
-- a few paragraphs, maybe a formula or two, some numbers, or a crude
diagram.
No one believes his abduction story, outside the hard core folks. Pissed off
and despondent, he later remembers what he memorized, writes it down, gives
it to Earl whose son is at college. Then shit happens.
The community of mathematicians/physicists/whoever determine that this is an
answer to Problem ZZZ, an astounding and inexplicable event. The information
on the card cannot be an accident, not some few random-looking digits, but
text that Joe was able to memorize, but no one on earth could possibly
devise at this time. So we know that Joe actually had a close encounter.
But to the point, what information could be on that card? (Physical
artifacts don't apply here -- I want information as proof, not stuff).
You have given a great answer: the factors of F20 (how about F21, or F30?).
Here are a few I thought of, but don't think are very good:
- A physical constant given to large precision. (Too difficult to
verify in the near term.)
- A counterexample to Fermats Last theorem. (Too late for that) Or,
conversely
- A ten-line proof of FLT, like the one Fermat couldn't fit in the
margin.
- A proof of another long outstanding conjecture.
- TOE (theory of everything) in three paragraphs.
- Prediction of something strange that will happen next
week/month/year, and does. (Too easy, and not fundamentally interesting.)
- what else...
What else could Mr Sixpack give us that would be incontrovertible proof of
his visit?
Cheers.
------------------------------
From: Kamran A Kashef <[EMAIL PROTECTED]>
Subject: TWInKLE
Date: Fri, 04 May 2001 01:57:03 GMT
For those of you familiar with Adi Shamir's TWInKLE, I have a question.
I understand the QS Factoriing Algorithm.
I understand RSA.
I understand the frequency/flash relationship.
I DON'T understand why the device works. It seems to extract numbers based
on 'y', but we are interested in y^2 mod z (where z = p*q). I do not see
how knowledge of a property of y help to tell you if y^2 mod z will factor
over B.
If you understand what is going on here PLEASE HELP. I've looked and asked
around for months and cannot get this cleared up. Thanks,
Kamran Kashef
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Encryption Algorythm
Date: Fri, 04 May 2001 01:58:36 GMT
"EE" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Is there a way to know if an encryption algorithm is secure? I would also
> like to know how strong this algorithm is.
Yes.
What algorithm against what attacks? Your question is not complete
Tom
------------------------------
From: billt <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Fri, 04 May 2001 02:09:36 GMT
In article <FLbH6.98588$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
>
> "Leonard R. Budney" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > > > > Rijndael WAS NOT MADE BY AMERICANS.
> > >
> > > Why would the **US** ITAR have anything todo witht the validitity of
> > > a Belgium block cipher?
> >
> > If you're going to be so snooty--and you are--learn to read. He didn't
> > ask about the validity of the cipher. He lives in the US. He wants to
> > implement the cipher. He doesn't want to go to jail. So he asked a
> > sensible question on this list. If you don't know the answer, shut yer
> > cakehole.
>
> Then he should ask the right question which is "Is it legal to use 256-bit
> symmetric keys in the US". This has nothing todo with AES or possible
> backdoors.
>
> Tom
>
Clearly, he didn't have available your helpful helpfulness, not to mention
your wit, precision, intelligence, thoughtfulness and wisdom, when he raised
his hand and asked a question.
The foolish person who doesn't know how to ask "the right question" should
have been raised by YOUR mother and father. We see they did a perfect job on
you.
Have a strict and tedious rest of your life.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: Fri, 04 May 2001 02:48:54 GMT
"billt" <[EMAIL PROTECTED]> wrote in message
news:AboI6.37185$[EMAIL PROTECTED]...
> In article <FLbH6.98588$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
> >
> > "Leonard R. Budney" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > > > > > Rijndael WAS NOT MADE BY AMERICANS.
> > > >
> > > > Why would the **US** ITAR have anything todo witht the validitity of
> > > > a Belgium block cipher?
> > >
> > > If you're going to be so snooty--and you are--learn to read. He didn't
> > > ask about the validity of the cipher. He lives in the US. He wants to
> > > implement the cipher. He doesn't want to go to jail. So he asked a
> > > sensible question on this list. If you don't know the answer, shut yer
> > > cakehole.
> >
> > Then he should ask the right question which is "Is it legal to use
256-bit
> > symmetric keys in the US". This has nothing todo with AES or possible
> > backdoors.
> >
> > Tom
> >
>
>
> Clearly, he didn't have available your helpful helpfulness, not to mention
> your wit, precision, intelligence, thoughtfulness and wisdom, when he
raised
> his hand and asked a question.
>
> The foolish person who doesn't know how to ask "the right question" should
> have been raised by YOUR mother and father. We see they did a perfect job
on
> you.
>
> Have a strict and tedious rest of your life.
Je t'aime beaucoup.
Tom
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: GNFS source code?
Date: Fri, 04 May 2001 02:53:04 GMT
Look for Dr. A. Lenstra's LIP packages. They're the ones responsible
for the largest RSA challenge crack.
JLC
Ben Wellborn wrote:
>
> Does anyone know where I can acquire source to the General Number Field
> Sieve (or even the Special Number Field Sieve) ??
> I've heard it's publicly available.
> I'm finishing construction of a beowulf, and I want to put it through
> it's paces.
> -Ben
------------------------------
From: jlcooke <[EMAIL PROTECTED]>
Subject: Re: Rijndael Galois Field construction problem.
Date: Fri, 04 May 2001 03:03:47 GMT
My pardon. 0 is not in a multiplicative group. The trivial element
was over looked. Let me restate:
All but the zero element is in the group. Otherwise the GF(2^8) in
Rijndael wouldn't be reversible.
JLC
Walter Hofmann wrote:
>
> On 2 May 2001 05:03:38 GMT, David Wagner <[EMAIL PROTECTED]> wrote:
> >
> >Maybe I don't understand finite field arithmetic well enough, but this
> >remark doesn't look right to me. In particular, the multiplicative group
> >GF(256)^* has 255 elements, which is not prime, so not all elements are
> >generators.
>
> Every finite subgroup of the multiplicatice group of a field is cyclic.
> Therefore the number of generators is phi(255)=128.
>
> >If g is a generator, then g^3 and g^5 are not generators of
> >the multiplicative group (to give two examples) since 3 and 5 divide 255.
>
> Exactly.
>
> >Also, 0 is not a generator. Did I misunderstand something?
>
> 0 is not an element of the multiplicative group.
>
> Walter
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: GNFS source code?
Date: Fri, 04 May 2001 03:07:22 GMT
"jlcooke" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Look for Dr. A. Lenstra's LIP packages. They're the ones responsible
> for the largest RSA challenge crack.
Afaik LIP is only a large integer package.
Tom
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: GCHQ Reorganization ? [Spoiler]
Date: Fri, 04 May 2001 03:39:13 GMT
On Tue, 01 May 2001 09:51:05 -0700, Jim Gillogly <[EMAIL PROTECTED]> wrote,
in part:
>I notice there's a Baconian cipher on the first line of that page
>in the roman/bold font that says "CHALLENGING".
I saw there was something there, but I couldn't get a readable message
out of it. I got dibnnfphkph and didn't recognize it as being
displaced by one Caesar step - I tried Bacon's original cipher to get
that, and I also tried 5-level code, but I didn't think of straight
binary (00001 = A instead of 00000 = A).
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
From: Ben Smith <[EMAIL PROTECTED]>
Subject: Re: GNFS source code?
Date: Fri, 4 May 2001 14:08:16 +1000
On Thu, 3 May 2001, Ben Wellborn wrote:
> Does anyone know where I can acquire source to the General Number Field
> Sieve (or even the Special Number Field Sieve) ??
> I've heard it's publicly available.
> I'm finishing construction of a beowulf, and I want to put it through
> it's paces.
There aren't many full-strength GNFSs in the world. I've worked on one,
and I've never heard of a decent publicly-available one (in source form).
ben
--
Always - what does that mean?
Forever - what does that mean?
It means we'll manage
-- Tricky, Christiansands
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: TWInKLE
Date: Fri, 4 May 2001 04:03:05 GMT
In article <P%nI6.483$[EMAIL PROTECTED]>
Kamran A Kashef <[EMAIL PROTECTED]> writes:
>For those of you familiar with Adi Shamir's TWInKLE, I have a question.
>I understand the QS Factoriing Algorithm.
>I understand RSA.
>I understand the frequency/flash relationship.
>I DON'T understand why the device works. It seems to extract numbers based
>on 'y', but we are interested in y^2 mod z (where z = p*q). I do not see
>how knowledge of a property of y help to tell you if y^2 mod z will factor
>over B.
The multiple of N = p*q to subtract is fixed (until one changes
polynomials). The simplest QS looks for smooth y^2 - N for y near
sqrt(N). For each prime r in the factor base B, knowing
(y mod r) determines whether r divides (y^2 - N).
For the appropriate y's, a quantum of light with magnitude log(r)
will shine. All shine at the same time for a fixed y.
If enough light shines at onced, then y^2 - N is potentially smooth.
--
The 21st century is starting after 20 centuries complete,
but we say someone is age 21 after 21 years (plus fetus-hood) complete.
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
Subject: Re: How much math is required to study this?
From: [EMAIL PROTECTED] (Xcott Craver)
Date: Fri, 04 May 2001 04:51:14 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>I just got my copy of Neils Book today... I skimed thru it (I like page 160
>:-). It's a very good looking book (I haven't read it through) but what I
>have read is very concise, easy to follow etc.
Arto Salomaa's book "Public Key Cryptography" is along the lines
of Koblitz's book, very readable, and maybe has a wider focus.
It's got a chapter on protocols, and a nice discussion of
other, weirder PK systems that are less number-theoretical and
less explored.
>Tom
-S
[And all the ciphertext examples are about saunas.]
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Free Triple DES Source code is needed.
Date: 4 May 2001 05:17:34 GMT
In <rhlI6.389$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
]I have looked every where on the web to find a Free C/C++ Source Code
]implementation of Triple-DES.
]I have found some, but it either has a damaged zip or tar file.
ftp://psych.psy.uq.edu.au/pub/Crypto/DES/
libdes.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Free Triple DES Source code is needed.
Date: 4 May 2001 05:20:45 GMT
In <8AlI6.9614$[EMAIL PROTECTED]> "Tom St Denis"
<[EMAIL PROTECTED]> writes:
...
]Third why are you using the aging 3DES? Is it for some compliancy issue?
]If so, well I feel for ya. If not, I suggest you modernize your crypto
]knowledge (if the algorithm is older than you or any of your school-going
]children it's outdated. As for me DES is about 5 years older then I am
]...). This is not to say AES will be "worthless" in 2006 or so but just
]that DES is fairly old, inefficient, not terribly secure and generally just
]a bad cipher.
]Nuff ranting. If you really really need some check out
Yes, it is ranting. DES has survived more examination than any of the
modern algorithms. It's key problem is a small key space. Triple DES
solves that problem.
It is not terribly fast, but it is certainly not a "bad cipher".
]http://the.wiretapped.net/security/cryptography/algorithms/
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 3 May 2001 22:49:37 -0700
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>I have a perfect OTP source and I have n messages, which
>for simplicity may be assumedd to be of the same length.
>I encrypt these via xor with n segments of the OTP. Am I
>sure that the opponent can't decrypt any of them? If no,
If you choose, fix, and commit to your message, and then generate a pad
and use it, that's secure. This means that you choose what message you
will send, and then you determine the pad, and use the pad you generate
*no matter what* that pad happens to be. That scenario (assuming an
appropriate generator) has the perfect secrecy property.
It is also secure to generate the pad (with an appropriate generator) in
advance and then not look at it, or look at it but ignore it COMPLETELY,
until after you have chosen your message.
It is not perfectly secure to change your message, or change the order of
messages, or change the wording of your message, or anything like that,
based on knowledge of the pad.
>segments that fail that. I choose to encrypt the n1 type
>A messages with the n1 segments that pass my test and
>the the n2 type B messages with the remaining n2
>segments. Is this o.k. or not? If not why? (Does the
No. In this case, you are looking at the pad, and only after looking at
it are you choosing which message to encrypt with which pad. As a result,
the pad and message are not independent. Independence of pad and
message is one of the requirements of the perfect secrecy theorem.
Suppose the pads and messages were all independent, and I knew them all,
and your selection procedure, but I didn't know the ciphertext or which
pads went with which messages. If that were true, then I should be unable
to guess which pads you chose for which messages. But in the scenario you
describe, I can look at a pad, see that it passes the test, and guess that
you used it with a "high security" message - or see that it fails the
statistical test and guess that you used it with a "low security" message.
In your scenario, pads and messages are not independent. The conditional
probability of you choosing a given pad for a specific message is not the
same as the probability of you choosing that pad for any arbitrary
message. By definition, they are not independent. Independence of pads
and messages is a requirement for perfect secrecy. The requirements for
perfect secrecy are not met in your scenario.
The fact that you're still using the rejected pad segment for some other
message, instead of discarding it entirely, is irrelevant. What counts is
that by changing the pad/message mapping based on the statistical tests,
you have destroyed the independence of pad and message, and Shannon says
you're not allowed to do that. Independence of pad and message is a
requirement for the perfect secrecy of the OTP.
--
Matthew Skala
[EMAIL PROTECTED] "I fish stranger things than you
http://www.islandnet.com/~mskala/ out of my granola every morning."
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
