Cryptography-Digest Digest #414, Volume #13 Wed, 3 Jan 01 00:13:01 EST
Contents:
New cipher design/online lab info ("Justin T.")
Re: computing RSA keys ([EMAIL PROTECTED])
Re: computing RSA keys ([EMAIL PROTECTED])
Book buying decision (Stinson vs Konheim) (Don Baldwin)
Re: GOST 28147-89 ("[Basic]")
Error Correction in the CRT Secret Sharing Scheme. ("Matt Timmermans")
Re: Very Simple Gift Certificate Scheme (David A Molnar)
Re: Can anyone break these cryptograms? (Richard John Cavell)
Re: Book buying decision (Stinson vs Konheim) (Jim Gillogly)
Sapphire sapphire on the wall whose the fairest ... ([EMAIL PROTECTED])
Re: Very Simple Gift Certificate Scheme ("John A. Malley")
----------------------------------------------------------------------------
From: "Justin T." <[EMAIL PROTECTED]>
Subject: New cipher design/online lab info
Date: Tue, 2 Jan 2001 21:10:21 -0500
How's it goin' ya'll. I've recently thrown together a quick website that
will feature my new security software. Along with a new cipher design, I've
developed internet-ready programs dealing with the OTP method. Although
this is to most an impractical method, I'm testing different methods to try
and improve it. If you'd like to take a look at the site, still under
construction by the way, feel free to. Also, when I get it up and running,
I'd appreciate some any feedback, whether it be criticism or praise....I'm
in this because it's what I do and the only way I can improve is to
learn...so I'm open to any opinions. If this doesn't interest you, that's
aight with me, but if it is of any interest to you, feel free to contact me
at [EMAIL PROTECTED] and visit my website at
http://www.twenty-one-security.net
Thanks for your time...
JT
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: computing RSA keys
Date: Wed, 03 Jan 2001 02:12:09 GMT
Bob, I apologize that I was not consistent in my notation, and that my
knowledge of number theory and it's associated language is quite
limited.
In article <92rg5j$b0$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> > then calculate (p-1)(q-1).
> >
> > Here's the trick I found.. I calculate a random n and find
> > (p-1)(q-1) * n + 1
>
> This makes no sense. What is this number supposed to be?
> And if p and q are n-bit primes (as you say above), then this
> number will be random in length as well. Or are you using n to
> mean different things (here and above)? That is a no-no.
Aparently I'm taking a rather different aproach than is traditional for
generating RSA keys.
You are right, n here is different from my n-bit keys. My mistake.
(Ignoring "n"-bit from now on.) N is simply a random number with
keysize-in-bits/(16+6) bits. (Its size was chosen experimentally and
isn't very important.) (p-1)(q-1)*n + 1 is only a little longer than pq.
> > this almost always factors easily.
>
> Huh? What are you using this number for??? And if factors
> easily, then p,q,n are too small.
When I say it factors easily, what I'm saying is that it nearly always
has multiple prime factors < 500. Perhaps "Factors easily" should be
replaced with "can easily be found to have factors (ie isn't prime)".
This was very important to me, because rather than starting with e (as
I'm now informed most RSA key generation schemes do) I start with p and
q and then attempt to find a valid d and e. It is important to me that
I can easily find factors because these "easy factors" become my e and
the what's left (ie ((p-1)(q-1)*n + 1)/e ) becomes d.
> > The trouble is that the result
>
> What "result"????
The resulting d and e
> > often has a public exponent which is
> > relatively small (between 5 and 10^5).
>
> Huh? This makes no sense either. You always choose e FIRST,
> BEFORE compunting p & q.
Why is it done this way? Perhaps there's another way? Or have I broken
some rule not spelled out in the "The Mathematical Guts of RSA
Encryption" article on which I based my code.
> May I suggest you do some reading? You seem to lack a basic
> understanding of terminlogy. The public key is a pair (e,N)
> where N = pq and (e, (p-1)(q-1)) = 1. The public key is not
> a single number. Do you mean the public exponent is 7?
I've been doing quite a bit of reading, and expect to continue to do
so, though I have to admit that this is more of a hobby than vocation.
> > someone might easily calculate a modulated 7th-root
>
> What is a "modulated" 7-th root? Do you mean "modular"???
I don't know if I mean modular -- I don't know the language. I mean
something like this:
Given EncryptedText, PublicModulo, PublicExponent=7
until(EncryptedText ^ (1/7) is a whole number) {
EncryptedText+=PublicModulo
}
-- we now have a value which could be the plaintext
It seems to me that the less the value of the public exponent, the
greater the chance that the first whole-number root would be the
plaintext... But I'm no expert.
> Finding the 7'th root of an integer mod pq is easy if one knows
> p & q, and very hard otherwise. All known methods are P-time
> equivalent to factoring pq. RSA would not work, otherwise.
I understood that to be the underpinnings of RSA, but I don't
understand why my silly algorythm above (while being rather time
consuming for larger public exponents) wouldn't work, and it presumes
nothing on p or q, only the public modulo.
> > (Sorry I
> > don't know the correct mathmatical language for this.)
>
> Don't you think you should learn it? How can you hope to
> undertake an implementation if you don't know the math?
An excellent question, and here you see the reason of my post. However,
there's a marked difference in knowing the math and knowing the
language well enough to pose a question without sounding a fool. (And
of course, the only foolish question is the one un-asked, right?)
> > Am I understand the situation?
> >
> > Is there a better way to calculate the multiplicative inverse?
>
> Better way than what????
Better than using my mysterious random n and factoring the result to
render d and e.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: computing RSA keys
Date: Wed, 03 Jan 2001 02:19:14 GMT
In article <92t7gf$2as$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Bill Unruh) wrote:
> Actually, one usually picks a public exponent like 5 17 33 --ie 2^n+1
to
> make the calculation of the encrypted message easy for the sender
I didn't know this, but I understand it.
> This appears to be hard-- ie as hard as the factoring.
Please see my previous post (in reply to Bob Silverman) for the
algorythm I had in mind...
> NOte, make sure that your message to be sent is substantially larger
> than (pq)^(1/7) ( assuming you use 7 as the public exponenet) or it is
> trivial to take the seventh root. (The usual way is either to pad with
> zeros to the right bring the length of the message up to the length of
> pq, or to pad with 10000... to the left to again bring it up to the
> length. Or pad with random digits and put in a byte telling the length
> of the real message.
Yes... I'm generating session keys, so I can make them whatever length
I like -- in fact, the longer the better.
Thanks!
john
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Don Baldwin)
Subject: Book buying decision (Stinson vs Konheim)
Date: 2 Jan 2001 18:39:46 -0800
I'm looking at buying either Alan Konheim's "Cryptography, a primer"
or Douglas Stinson's "Cryptography :theory and practice" (I'm
sure I'll own both eventualy, though).
What I'm looking for are mathematic approaches to cryptanalyzing
some classical cyphers through modern cyphers. That sounds
more like Konheim to me but I thought I'd ask more experienced
people what they thought.
Does Stinson cover classical cryptography or just modern block
cyphers?
Other impressions regarding either book would be GREATLY
appreciated.
Thanks!
Don
------------------------------
From: "[Basic]" <[EMAIL PROTECTED]>
Subject: Re: GOST 28147-89
Date: Wed, 3 Jan 2001 03:42:00 +0100
"Tom St Denis" <[EMAIL PROTECTED]> schrieb im Newsbeitrag
news:92tvu3$hr$[EMAIL PROTECTED]...
> In article <92tu70$e3l$01$[EMAIL PROTECTED]>,
> "[Basic]" <[EMAIL PROTECTED]> wrote:
> >
> > "Tom St Denis" <[EMAIL PROTECTED]> schrieb im Newsbeitrag
> > news:92tnon$pkl$[EMAIL PROTECTED]...
> > > In article <92tliv$a5v$01$[EMAIL PROTECTED]>,
> > > "[Basic]" <[EMAIL PROTECTED]> wrote:
> > > > As I don't speak c/c++ I dont have any compiler for it.
> > > >
> > > > So please now stop talking, take your masterpiece, encrypt
> something
> > > in ecb
> > > > mode and post the details here.
> > >
> > > Why if you can't program then what does it matter?
> >
> > the only language i speak is x68 assembler
> >
> > >
> > > Anyways...
> > >
> > > key: 00 01 02 03 04 05 06 07 .. .. ..
> > > ct : aa 6e 47 af 95 1c 9f 2a
> > > pt : 00 01 02 03 04 05 06 07
> >
> > thx for you work but without knowledge of the SBoxes that were used
> this
> > example is useless.
> > btw post if you increment the key in hex and it's half the work
>
> The sboxes are in the source code I referenced. Just pull em out!
>
> And the key bytes go from 0 to 31 (decimal).
>
> Tom
>
>
> Sent via Deja.com
> http://www.deja.com/
thx a lot for your work but ive still questions...
i dont understand the make_sboxes sub in your code. such sbox manipulating
is not described in the gost 28147-89 specifications.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Error Correction in the CRT Secret Sharing Scheme.
Date: Wed, 03 Jan 2001 03:19:10 GMT
Since a few of us have been reexamining CRT stuff lately, I thought I'd pass
on this very cool paper. It will allow me to correct for errors or
malicious modifications in the information distribution scheme I spoke of
several threads ago. He only treats CRT with primes, but it will work for
polynomials in GF(2^x) too (but not, I think, with the O(N log N) complexity
he gets).
http://www.toc.lcs.mit.edu/~madhu/papers/odedana.ps
The rest of his publicly avalable papers are here:
http://www.toc.lcs.mit.edu/~madhu/papers.html
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Very Simple Gift Certificate Scheme
Date: 3 Jan 2001 03:28:28 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>> Could you include in the next version of the paper some discussion of
> who
>> gets it wrong, and what they do wrong?
> Well it's just a small snippet paper since I have seen people ask this
> question before. Often you goto sites like mail.yahoo.com and get
> tokens "mail.yahoo.com/read.pl?rand=294724892734" where rand= is a
> certificate of sorts. I wonder how they made it...
> I dunno.
OK. It's just that you presented it as "something that people often get
wrong," so I thought you had noticed some problems. Sounds like you have -
sending such a certificate in the clear probably isn't a good idea.
When proposing a new solution to a problem, it's important to show what
the other proposed solutions are - and how your solution is different.
Ideally, how your solution is _better_.
Otherwise readers like me, who aren't familiar with online gift
certificate practice, will wonder why you did this and what the
alternatives are.
To take it farther, it would be interesting to see an analysis of what the
particular pitfalls and issues are in online gift certificates. In
particular, how are they different from digital cash if they are at all?
Bryan Olson brought up some other neat questions - can you design gift
certificates which are anonymous? do not require a centralized storage for
clearing spent certificates?
-David
------------------------------
From: Richard John Cavell <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: Can anyone break these cryptograms?
Date: Wed, 3 Jan 2001 14:43:30 +1100
On Sun, 31 Dec 2000, daniel mcgrath wrote:
> slight difference. I would be interested in seeing if any of you on
> rec.puzzles or sci.crypt are able to decipher the messages, or at
> least make hypotheses.
I tried for 3 hours last night using pen and paper and failed. After some
spoiler space, I'll tell you how I went about it:
The letters 'U', 'I', and to a lesser extent, 'X' are the most common. I
hypothesised that the cryptograms are alphabetical substitutions with E,T,
and A probably being U, I, and or X. I substituted every combination.
The only one that made sense was:
U = E
X = T
I = probably I or R
There are certain combinations of U,X, and I for which only certain words
are possible. In which case the word 'teenage' appears in the first
cipher, but then gobbledegook appears in the second if I use the same key.
So I then tried simply rotating the alphabet by a fixed amount. I tried
every possible rotation and it all comes out as garbage. I tried using
the first letter of every 5-letter combination as some kind of key to
decrypting the next four by rotation, and it comes out as garbage.
I also postulate that the ciphers will contain the words 'happy' or
'merry' or something. I then looked for sequences where there are two
letters in a row (excluding the three X's in a row in the second cipher).
I looked at the letters immediately following and wondered whether these
are likely to be the letter 'Y'. I also thought you may have written the
messages backwards, so I looked at the letter preceding the double letter
sequences.
But I find no real pattern.
My current hypothesis is that you have used a key that rotates after every
letter, so that the substitution key is some function of the letter's
position in the text.
I think it is not significant that you broke the cipher into 5-letter
blocks. Partly because I can find nothing special about the first letters
of each group when considered separately to the other 4, and partly
because your last message runs out after only 4 letters on the last line.
Okay, I give up.
==============
Richard Cavell
Medical Student, Debater, Chess Player, etc.
[EMAIL PROTECTED]
Newsgroups - Please keep any discussion on the group, and copy your
replies to me via email. (Server problems).
Do you want filthy language and abuse sent back to you? Just send me bulk
unsolicited email! Don't say you didn't ask for it!
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Book buying decision (Stinson vs Konheim)
Date: Tue, 02 Jan 2001 20:15:18 -0800
Don Baldwin wrote:
>
> I'm looking at buying either Alan Konheim's "Cryptography, a primer"
> or Douglas Stinson's "Cryptography :theory and practice" (I'm
> sure I'll own both eventualy, though).
>
> What I'm looking for are mathematic approaches to cryptanalyzing
> some classical cyphers through modern cyphers. That sounds
> more like Konheim to me but I thought I'd ask more experienced
> people what they thought.
Definitely get both, but get Stinson first unless you're mathematically
strong. Stinson starts easier. But for classical ciphers you'd be
better off with the "Military Cryptanalytics" series by Callimahos
and Friedman published by Aegean Park Press, available also from
Classical Crypto Books ([EMAIL PROTECTED]) -- the price list and
stuff are available in PDF form from the same address.
> Does Stinson cover classical cryptography or just modern block
> cyphers?
The Table of Contents and other stuff is at
http://www.cacr.math.uwaterloo.ca/~dstinson/CTAP.html
--
Jim Gillogly
Mersday, 12 Afteryule S.R. 2001, 04:06
12.19.7.15.7, 12 Manik 10 Kankin, First Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.geo.earthquakes,alt.fluid-dynamics,alt.sci.astro.eclipses
Subject: Sapphire sapphire on the wall whose the fairest ...
Date: Wed, 03 Jan 2001 04:31:37 GMT
Re: Comets, Meteors, and Mitotic Spindles
Yes, you are quite correct!
Asteroids are NOT composed of the same "matter" as meteors or comets.
The meteors that hit Austria long ago created the salt mines that led
to the naming of Salzburg. And that big big big meteor redefined
Celtic Germany that hit Reis [Bavaria] and Steinheim [Nord-Rhein
Westphalen] some time ago.
The Rugieri Tribe of the Bodden Strait DID survive the blast however,
and the Rugen Islands still exhibit massive chalk cliffs and authentic
sea dolomite formations that provided shelter for the survivors.
Norway suffered very dearly and has such spindly and ropey and fibrous
rather than hard wooded trees, as a result [I believe the Beatles were
alluding to this in NORWEGIAN WOOD]. The Norwegian Maple, a very soft
tree, is now called A. Saccharinum, ... perhaps named after a star
somewhere, or even a long forgotten asteroid.
You forgot to mention that boron is often found in meteorites, and not
in asteroid debris.
Of course, moldavite comes from meteors, and not asteroids.
Wasn't ancient Cambodia blasted by a meteor too? [Muong Nong?]
I believe "corundum" comes from asteroids, aka sapphire, named after
Saphos. It is a soapy crystalline substance ... at bottom, when
diligently tested, as if a diamond.
Wasn't 'Sapphira' another name for Aster in the time of the Moabs?
I never heard of mitotic spindles being an element of asteroids or
asters, but I'm familiar with the penicillium called griseofulvin, that
uses mitotic spindles, microtubles, and interferes with cell wall
components and chemistry.
Who will win this debate over asteroidal supremecy or meteoric
mastery? The Vatican or the Smithsonian? Isn't it quite exciting!
Chemosh
In article <92tlpd$nnn$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> RE: http://www.geocities.com/antarii_rescue/index.html
> http://www.geocities.com/antarii_rescue/index2.html
> http://www.geocities.com/antarii_rescue/antares.html
> http://www.geocities.com/antarii_rescue/aldebaran.html
> http://www.angelfire.com/de/CassandraCrossing/PAGE3B.html
>
> The Feb 2001 SKY & TELESCOPE magazine published a story by the Vatican
> astronomer Guy Consolmagno titled "The Story of Space Rocks".
>
> He was none too pleased with the recent Smithsonian Press book
> called "Asteroids: A History".
>
> Myself, I always thought it was clear to all schoolchildren that
> asteroids are lava chunks spewed out by volcanoes here on Earth and
> elsewhere, that fly out of the planet's orbit into space.
>
> Meteors have parts iron and parts silicon. Asteroids have next to no
> iron. When meteors slam into earth they cause a thermonuclear
> explosion and leave much melted glass [tektites], and large salt
domes.
>
> To wit: Marquez Dome of Texas; the Upheaval Dome of Moab, UT; the
> Ayers Rock region of Australia; the Serpent Mound of Ohio, USA; the
> Libyan Desert; the Barringer Crater of AZ; and the underwater crater
of
> the Barents Sea [the most salty ocean].
>
> The volcanic underwater mountain ridges of the Azores are asteroidal;
> as are the Pacific Fire Rim underwater mountain ranges; the whole area
> of Hawaii; most of Icelandic quarters; the Mauritius Island
archepilago
> in the African Indian Ocean; et al.
>
> These asteroidal volcanic areas seem to be seldom, if ever, bombarded
> by comets or meteors. Why?
>
> Could Signor Consolmagno please explain this remarkable phenomena!
>
> Could it go back to the arguments of the ancient Ammonites, before
they
> were turned to pillars of salt [Lot was one of their people], that
> concern the difference between asters and astrals?
>
> An aster is a fake star and not genuine. It is also the name of
> tubular flowers, tulip like, in China.
>
> An astral is a real star and has a genuine mitotic and meitotic
> component.
>
> An aster has a spurious radial arrangement around a spindle-like
> mitotic and meiotic cyst.
>
> Hope this stimulates debate.
>
> M. Moroni
>
> In article <[EMAIL PROTECTED]>,
> "Roy Sharif M. Sison" <[EMAIL PROTECTED]> wrote:
> > A new earthquake just struck Southern Philippines a few moments ago.
> > It's either a new quake or a strong shock after the M7.2 submarine
> quake
> > yesterday afternoon.> > Thanks.
> >
> > Regards,
> >
> > Roy
> >
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Very Simple Gift Certificate Scheme
Date: Tue, 02 Jan 2001 21:01:14 -0800
Tom St Denis wrote:
>
> My very-simple-most-likely-thought-of-before-but-never-really-discussed-
> because-too-many-people-get-this-stuff-wrong paper on simple gift
> certificates.
>
> http://www.geocities.com/tomstdenis/files/gcert.ps.gz
>
> Tom
>
> Sent via Deja.com
> http://www.deja.com/
Just so I'm clear on the protocol after reading the PDF paper:
Alice generates a secret key K. To issue certificates, Alice generates
a new serial number Sn and concatenates ( Sn | K ) into one bit string
(yes?)
Alice hashes the concatentated string as H = hash( Sn | K ), and
provides < H, Sn > as the certificate to Bob.
Bob can pass the certificate to a third party (Carol) as a gift, and
Carol can claim the value of the certificate by presenting < H, Sn > to
Alice.
Alice checks the validity of the certificate by recalculating H from
hash( Sn | K ) to prove to herself that this IS a serial number she
issued.
Alice must also check that this serial number was not yet claimed. If it
wasn't she gives its equivalent in value to Carol.
If it was already claimed, she apologizes to Carol and tells her she's
out of luck.
To prevent this scenario, Alice must send the certificate to Bob through
a secure channel, AND, Bob must send to to Carol (as a gift) through a
secure channel, AND, Carol must present it back to Alice (when she
claims her gift's value) through a secure channel.
If Carol is ever told the certificate was already used then, provided
the channels remained secure, either Bob or Alice used the certificate
before she did. If the secure channels involve an authentication
protocol,then the transaction claiming the certificate on a secure
channel records the identity of the cuplrit who actually exercised the
certificate.
So why does Alice need the secure hash on (Sn | K)? What does the hash
provide Alice, Bob and Carol? Suppose they all communicate across
secure channels (and the cipher is non-malleable and semantically
secure) AND only Alice knows which random serial numbers were ever
actually generated?
Alice randomly selects k-bit serial numbers over the range 0 - (2^k - 1)
with uniform probability.
She records the random Sn she issues. Alice sends just the Sn to Bob
through a non-malleable, semantically secure channel.
Bob relays the Sn to Carol again through a non-malleable, semantically
secure channel.
Eve has her work cut out for her. She can't do much of anything with
what she intercepts. Eve can't alter the messages or learn a single bit
about the messages. So the hash doesn't need to protect anything for
Alice, Bob and Carol's benefit.
Bob could claim the Sn before Carol does after he gives it to her as a
present. Alice gives the value of the certificate (Sn) to whomever
claims it first. The hash doesn't protect against that.
Carol or Bob could try to generate a random Serial number and see if
Alice would accept it. Their success depends on the number of serial
numbers previously generated and yet unclaimed. If 2^s serial numbers
out of the total 2^k possible serial numbers ( s < k ) were generated at
time t, then the probability of randomly generating one of those
recognized Sn is 2^(s-k). And only a fraction of those recognized
serial numbers may actually remain unclaimed. Alice chooses the number
of bits k in a serial number to be great enough that the probability of
a random guess hitting an unclaimed number is an acceptable risk to her.
When Alice gets a serial number she just checks in her database of
issued serial numbers. If it doesn't match then she doesn't honor it.
If it does match and it was previously claimed, she doesn't honor it. If
it matches and it hasn't been claimed before, she honors it.
So I'm missing something about the use of the hash. It's important for
some reason. Please help!
What does the hash help protect against if Alice, Bob and Carol pass the
certificates to one another via secure channels, only Alice knows the
complete set of serial numbers issued, and the serial numbers are
selected at random uniformly distributed across 0 - (2^k - 1)?
John A. Malley
[EMAIL PROTECTED]
------------------------------
** 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
******************************
