Cryptography-Digest Digest #207, Volume #14 Sun, 22 Apr 01 12:13:00 EDT
Contents:
Re: C code for GF mults ("Brian Gladman")
Re: basics of cryptography (John Savard)
Re: Censorship Threat at Information Hiding Workshop (David A Molnar)
Re: Hash function ("Jack Lindso")
Re: ancient secret writing (Jim Gillogly)
Re: basics of cryptography (Pille2)
Re: basics of cryptography (Pille2)
Re: Cryptanalysis Question: Determing The Algorithm? ("Dramar Ankalle")
Re: Can this be done? ("Mark Lomas")
PRNG quality ("William A. McKee")
Gurus please: -- show weaknesses (Brett)
Re: XOR TextBox Freeware: Very Lousy. ("Henrick Hellström")
Re: basics of cryptography (Brett)
Re: basics of cryptography (Daniel)
----------------------------------------------------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: C code for GF mults
Date: Sun, 22 Apr 2001 14:32:48 +0100
"Mike Rosing" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Jyrki Lahtonen wrote:
> > Define elements x_i recursively as follows:
Hi Mike,
> > x_0=1, and
> >
> > for i>0 let x_i be a root of the equation
> >
> > T^2+x_{i-1}T+1=0 (*)
> >
> > It is relatively straightforward to see that x_k then generates
> > (but is not primitive by a long shot) the field GF(2^(2^k)).
> > If memory serves me right, it even generates a normal base.
>
> It ain't straight forward for me, but let's see if I can get it
> eventually. For x_1 we have
>
> x_1^2 + x_1*x_0 + 1 = 0
>
> You're saying x_1 has to be 4 bits wide.
I don't think so since each iteration doubles the number of bits. SInce x_0
is 1 bit wide x_1 is 2 bits wide, not 4 bits wide. It is x_2 that is 4 bits
wide. Hence x_k is 2^k bits wide and hence represents field elements in
GF(2^(2^k)).
Since x_0 = 1, we have
> a very simple quadratic, but to solve it in GF(anything) we need
> pick (anything) first. Depending on what we pick, how do we know
> it's always 4 bits?
I think the idea is that of simple field extension. That is, if a quadratic
in a field has no solution in this field (it is irreducible if F), a new
field can be defined with elements Ax + B where A and B are each elements of
the original field and x is a root of the irreducible quadratic. Since A
and B are each n bits wide the representation of elements in the extended
field (A,B) - is 2n bits wide.
This is the same principle by which reals are extended to complex numbers -
by having two real numbers and the root 'i' of x^2+1=0 so that c = (x,y) = x
+ i y. Such field extensions will be covered in any standard book on finite
fields or abstract algebra (the one I use is 'Introduction to Finite Fileds
and Their Applications' by Lidl and Niederreiter, CUP).
> In the complex plane, T = (-1 +/- sqrt(-3))/2. This lies on the
> unit circle at 45 degrees, so it's the 4th root of unity. Is that
> how you figure the field size?
>
> Is T always the 2^k th root of unity if you use the 2^(k-1) root as
> a coefficient? Pretty cool :-)
I believe that there will also be an explanation along the lines you suggest
in terms of the n'th roots of unity. These roots can be expressed in terms
of finite fields (the cyclotomic fields) as well as in terms of complex
numbers. The relationship between the n'th roots of unity expressed in
terms of complex numbers and in terms of finite fields is itself an
interesting aspect of the subject.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: basics of cryptography
Date: Sun, 22 Apr 2001 15:00:05 GMT
On Sun, 22 Apr 2001 15:30:10 +0200, Pille2
<[EMAIL PROTECTED]> wrote, in part:
>I did and i´m not as stupid as it seems at least i think i´m not :)
>But nevertheless in none of these texts it is explained how i calculate the
>mentioned possibilities. I know what monoalphabetic and polyalphabetic is
>that was´nt my question.
How to calculate the number of ways a cipher may be keyed may indeed
not be spelled out in books on cryptography. But you might wish to
consult references on combinatorics for the needed background.
As Mr. St. Denis noted, a monalphabetic cipher can be arranged with
26! alphabets; the substitute for A can be any letter, that for B can
be any other letter, and so on, so the number is 26 * 25 * .... * 1.
For Vigenere, the number of possibilities depends on the length of the
key. So if the key is, for example, from 8 to 13 letters long, then
there are 26^8 + 26^9 + .... + 26^13 possible keys... but in that
case, the key will probably be a word, not a random string of letters,
so the number of keys is really much smaller.
The Enigma could be set up in an enormous number of ways, so some
indication of how to do this kind of calculation might be found in
some of the books on the Enigma.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Censorship Threat at Information Hiding Workshop
Date: 22 Apr 2001 14:33:40 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
>> It is an attack on individuals who dare fight corporate greed and
>> corporate welfare.
> Funny how pirates always find rationalizations like that.
Can we agree that Felten et. al. are not pirates? Even the SDMI foundation
acknowledges their good intentions - in the sense that they are not "out to
help anyone break anything." Neither do we know whether any of the authors
are anti-corporate.
-David
------------------------------
From: "Jack Lindso" <[EMAIL PROTECTED]>
Subject: Re: Hash function
Date: Sun, 22 Apr 2001 16:58:24 +0200
Hmmm, I'm sorry but could anyone comment on the hush algorithm in the
previous message. I'm quite aware of it's simplistic design however your
comments would help me alot.
Cheers.
--
Anticipating the future is all about envisioning the Infinity.
http://www.atstep.com
====================================================
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: ancient secret writing
Date: Sun, 22 Apr 2001 08:13:57 -0700
Mok-Kong Shen wrote:
>
> "Douglas A. Gwyn" wrote:
> >
> > John Savard wrote:
> > > image appears to be of shorthand, perhaps the well-known and
> > > still-used Pitman or Gregg.
> >
> > I tried posting a similar response, but Netscape died and I had to
> > tke care of other business. There are a zillion different schemes
> > of shorthand. Jim Gillogly has broken at least one of these. It's
> > similar to attacking a code system.
Four, I think. It's an interesting challenge: shorthand systms are
usually phonetic, so although there may be pattern words, your pattern
dictionaries are no help. The original post on this thread has fallen
off my Usenet provider and doesn't appeared to be archived on Google
or Etin (does anybody archive just sci.crypt?), but my cursory glance
at this one suggested that the 5 or 6 kinds of isolated characters are
vowels. If one were lucky that single postcard might be enough to
spot the system in a fat compendium of shorthand systems; otherwise
perhaps half a dozen postcards like that one might be enough. Fewer
if there are cribs.
> A related thought: There are, if I don't err, quite a
> number of archaeological findings with symbol sequences
> of yet unknown meaning. Are there any attempts to
> 'decrypt' these with the help of the now much advanced
> knowledge of crypto (in comparison to the time of
> 'decryption' of hieroglyphs)?
One of the more interesting of these is the Voynich Manuscript, which
may or may not have underlying meaning. So far advanced cryptanalysis
(as applied by Brig. Tiltman, W. F. Friedman, and the other leading
lights) has not availed to decrypt it.
--
Jim Gillogly
Hevensday, 26 Astron S.R. 2001, 17:35
12.19.8.2.12, 13 Eb 10 Pop, Seventh Lord of Night
------------------------------
From: Pille2 <[EMAIL PROTECTED]>
Subject: Re: basics of cryptography
Date: Sun, 22 Apr 2001 17:11:30 +0200
If you know so much why can´t you give the aswer?
And sorry because of probable/possible i´m not english nor american so my
english may not be the best.
Btw. I don´t want to wirte a book it´s just a work for a school lesson.
------------------------------
From: Pille2 <[EMAIL PROTECTED]>
Subject: Re: basics of cryptography
Date: Sun, 22 Apr 2001 17:14:22 +0200
in Beitrag [EMAIL PROTECTED] schrieb John Savard unter
[EMAIL PROTECTED] am 22.04.2001 17:00 Uhr:
> How to calculate the number of ways a cipher may be keyed may indeed
> not be spelled out in books on cryptography. But you might wish to
> consult references on combinatorics for the needed background.
>
> As Mr. St. Denis noted, a monalphabetic cipher can be arranged with
> 26! alphabets; the substitute for A can be any letter, that for B can
> be any other letter, and so on, so the number is 26 * 25 * .... * 1.
>
> For Vigenere, the number of possibilities depends on the length of the
> key. So if the key is, for example, from 8 to 13 letters long, then
> there are 26^8 + 26^9 + .... + 26^13 possible keys... but in that
> case, the key will probably be a word, not a random string of letters,
> so the number of keys is really much smaller.
>
> The Enigma could be set up in an enormous number of ways, so some
> indication of how to do this kind of calculation might be found in
> some of the books on the Enigma.
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
Thanks that was what i wanted to know...
Philipp
------------------------------
From: "Dramar Ankalle" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalysis Question: Determing The Algorithm?
Date: Sun, 22 Apr 2001 11:18:22 -0400
wtshaw <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <9btm4j$49q$[EMAIL PROTECTED]>, "Dramar Ankalle"
> <[EMAIL PROTECTED]> wrote:
>
>
> > > We have a new generation of children who don't like losing the big
game
> >
> > Why would children be in some big game?
> >
>
> > Children are doing this?
> > Send them to school, and dont take their money away if they get in
trouble
> >
>
> > Dogs that bite children get put down.
> >
> I'm not speaking of kids but of spoiled brats, many of who seek public
> office for serving themselves rather than the public. And, they should
> have their allowances cut.
> --
> Nafta, etc.? No way Jose.
Well you write children say children instead of spoiled brats.You wanna know
spoiled?I have, strangely enough, a black book of phone numbers from some
ex-stripper girlfriends that have current policians in them, and their drugs
of choice, and phone numbers.I think it is spoiled to turn around and punish
youthful discretion, being a youthfull ``disc ressor" themselves.I mean,
Navy Offers and Crystal meth in Long Beach?
Whats that all about?
Spoiled in Whittier,
A P O L L Y O N
------------------------------
From: "Mark Lomas" <[EMAIL PROTECTED]>
Subject: Re: Can this be done?
Date: Sun, 22 Apr 2001 09:17:45 +0100
"John Wasser" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <3ae12b5e$0$15023$[EMAIL PROTECTED]>, Mark Lomas
> <[EMAIL PROTECTED]> wrote:
>
> > If Bob receives two messages, one from Alice and one from Eve, each
> > containing a different public key, followed by similar messages from
both
> > Alice and Eve all of which are signed as you suggest, how can he tell
> > whether Eve is duplicating Alice's messages or Alice duplicating Eve's?
>
> He can't. That was not a requirement. The only requirement was that
> Bob be able to determine that a set of mesages all came from a source
> that knew some unspecified secret.
It may not have been stated explicitly, but it is requirement
implied by use of the word 'source'.
Alice was the source of the messages.
Eve duplicated those messages, but substituting a new key.
Let us assume that Eve sends one extra signed message.
This did not come from the same source as the original messages.
How can Bob tell?
Mark
------------------------------
Reply-To: "William A. McKee" <[EMAIL PROTECTED]>
From: "William A. McKee" <[EMAIL PROTECTED]>
Subject: PRNG quality
Date: Sun, 22 Apr 2001 15:45:53 GMT
I was wondering ... if you have two different PRNG (pseudo random number
generator) named P and Q, does the resulting PRNG (P xor Q) give you any
better (more random) results than just P or Q alone?
TIA,
Will.
--
William A. McKee <[EMAIL PROTECTED]>
http://www.cjkware.com/wamckee/
Asia Communications Quebec Inc.
http://www.cjkware.com/
"We're starfleet: weirdness is part of the job." - Janeway
"I have seen things I cannot deny." - Scully
PGP public key at http://www.cjkware.com/wamckee/pgp/ ( ID = 0x11162FF2)
Finger Print: F5B8 6251 050C 7595 6A84 6C37 6041 4258 1116 2FF2
"We need your help... " - http://www.distributed.net/
------------------------------
From: Brett <[EMAIL PROTECTED]>
Subject: Gurus please: -- show weaknesses
Date: Sun, 22 Apr 2001 11:57:34 -0400
Reply-To: [EMAIL PROTECTED]
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Hi,
I'm new to this group, but wonder if I can generate
interest in the following method of encryption, in hopes
that some of the more experienced of the group can point
out its weaknesses (if any).
It's based on the Vigenere cipher (at end of post
for those who need reminding), with a twist. I would
use it on messages that aren't very long (500 characters
or less).
I would encrypt the plaintext with a keyphrase (not
something simple as seen below, but some rediculous
jumble of unicode letters (65536 in all)) by a standard
Vigenere-like process. I would then select another new
key for the NEXT message to be sent (I don't want to
use the same key every time -- that would lead to break-
ability) and would encrypt this new key with the current
key.
I would then add a checksum to check for data
fidelity and to disuade tinkering with the code in
transit. I'll give an example using ASCII letters
rather than Unicode, as it'll be easier to follow.
The principle is the same (the ciphertext is based
on a 27x27 Vigenere square ... the 27th one is the
spacebar character " " ):
Current message: MY MESSAGE
Current key: STEVE JOBS
Next Key: BILL GATES
-- start encryption:
Key: STEVE JOBSSTEVE JOBS
Msg: MY MESSAGEBILL GATES
ciphertext: EREHJSBPIXUBQGEGKHGK
Then I put in some type of checksum of the two
halves of the plaintext message at the end ... say, I
add all the unicode values up of all the letters in the
plaintext message and put the last two digits of it at
the end, do the same with the new key to build a 4-digit
checksu,. So the transmitted item is this:
EREHJSBPIXUBQGEGKHGK1595
Thus, the current message and new key could be decrypted
on the other side with the current key, the new key for the
next message would be known by both sides, and the checksum
would exist to make sure no monkey-business happened in
between. This way, the keyphrase would never be used more
than once. The key would also never be shorter than the
message ... if the operator tried to encrypt a longer message
than the length of the key, two messages would be sent, one
with the current key for the first 500 letters, with the
second key attached, and the second message encrypted with
the second key and a third key attached.
Reasons for the above:
1) A key phrase of equal length to the plaintext makes
it a polyalphabetic substitution with up to 65536 alphabets
and up to 500 letters per key ... thus total keys are:
65536 ^ 500 (an enormous number I'm sure).
2) Since no repetition of the keyphrase is employed,
the cryptanalytic techniques of looking for repititions of
sets of letters like seeing "DWM" several times might
clue you in that this is "the" would not work. (Babbage
and Kasiski employed this technique to first crack the
Vigenere cipher about 150 years ago, but it relies heavily
on the key being repeated often on long messages to work)
The checksum defeats anyone who tries to paste in a
false second half to the transmitted passage (in attempt
to have the second computer send back a message encrypted
with some type of key the codecracker could use to his/her
advantage)
I would love any replies.
Brett
- ------- below this is Vigenere cipher for reference:
A B C D E F G H ... X Y Z %
---------------------------
A|B C D E F G ... Y Z % A
B|C D E F G ... Y Z % A B (I substituted
C|D E F G ... Y Z % A B C % for " " for
D|E F G ... Y Z % A B C D clarity)
etc.
Letter of plaintext on left, letter of key on top,
whatever these coordinates line up to ... key that letter
into as the ciphertext
But note, my Vigenere-style cipher would have 65536
rows and columns in it, not just 26.
- ----------
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3 for non-commercial use <http://www.pgp.com>
iQA/AwUBOuL/Z1msYkIq5977EQJMsACgnMOasB6uYduMZ8tErh/rQc3E+qUAoJep
p64v08hkxKUwjlny/PBCAkET
=ZGI6
=====END PGP SIGNATURE=====
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: XOR TextBox Freeware: Very Lousy.
Date: Sun, 22 Apr 2001 17:59:26 +0200
"David Schwartz" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
>
> Anthony Stephen Szopa wrote:
>
> > I am not the guy who said the XOR function is "wimpy or has a
> > straight forward crack"
> >
> > I am sure we all could use an extra $1000.
> >
> > But I don't see him offering.
>
> In any realistic application, the XOR function is crackable. Generally,
> you attack the means of distributing the OTP. The big flaw in XOR is it
> shifts the burden of keeping the cipher secure from the cipher itself to
> the user. If the user had a good, secure means of sending the OTP to the
> recipient, why wouldn't he just use that mechanism to transfer the
> plaintext itself?
Old question and IMHO still fomulated the wrong way. You should use an OTP
when you have a need to send messages more frequently than you are able to
exchange the OTP securely. So the answer is: Because he can't.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Brett <[EMAIL PROTECTED]>
Subject: Re: basics of cryptography
Date: Sun, 22 Apr 2001 12:03:36 -0400
Reply-To: [EMAIL PROTECTED]
Pille2 wrote:
> How do i calculate the possibilities for monoalphabetic and polyalphabetic
> ciphers or is there no difference?
For monoalphabetic cipher (substitution cipher seen in "cryto-quote"
newspaper games) the number of keys available is expressed in mathematics
as "25!" ("25 factorial") or 25 * 24 * 23 * 22 * 21 ... etc. If you allow
for some letters to represent themselves ("J" is "J") then it is 26!
For polyalphabetic ciphers (Vigenere style with a keyphrase) the
number of keys is (n ^ 26) where n is the number of characters in the
keyphrase.
Brett
------------------------------
From: Daniel <[EMAIL PROTECTED]>
Subject: Re: basics of cryptography
Date: Sun, 22 Apr 2001 18:08:43 +0200
On Sun, 22 Apr 2001 15:15:09 +0200, Pille2
<[EMAIL PROTECTED]> wrote:
>Hi!
>I´m writing a text about the basics of cryptography: In this work simple
>encryption methods are explained etc.
>Perhaps an easy question but how do i calculate the number of possibilities
>that exist for the encryption of a char. For example in the vigenere cipher.
>How do i calculate the possibilities for monoalphabetic and polyalphabetic
>ciphers or is there no difference?
>
>Sorry if the question is too stupid
>
>Philipp
Philipp,
Try the following links
http://www.und.nodak.edu/org/crypto/crypto/resources.html
http://www.simonsingh.com
http://home.ecn.ab.ca/~jsavard/crypto.htm
and for something more recent there always is:
http://fermat.ma.rhbnc.ac.uk/~fauzan/papers/report.pdf
Very recommended is the HAC for all crypto-math
http://www.cacr.math.uwaterloo.ca/hac/
Hope this is helpful to you.
Best regards,
Daniel
Best regards,
Daniel
------------------------------
** 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
******************************
