Cryptography-Digest Digest #343, Volume #10 Fri, 1 Oct 99 09:13:04 EDT
Contents:
Re: Perfect Shuffle Algorithm? (Dr D F Holt)
Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers (Paul Crowley)
Re: Cryptic manuscript... Help ([EMAIL PROTECTED])
Re: RSA-512: Weizmann Institute: London Times (Paul Crowley)
Re: RSA-512: Weizmann Institute: London Times ("NP")
Re: NEMA, Swiss cipher machine (drobick)
security: stream cipher ([EMAIL PROTECTED])
proof ([EMAIL PROTECTED])
Re: SNAKE Web Page ([EMAIL PROTECTED])
Re: Q: Burrows-Wheeler transform (Tom St Denis)
Re: msg for Dave Scott (jerome)
Re: Example of a one way function? ("Boris Kolar")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Dr D F Holt)
Crossposted-To: sci.stat.math,sci.math
Subject: Re: Perfect Shuffle Algorithm?
Date: 1 Oct 1999 10:06:51 GMT
In article <7t0rjk$oat$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Alan Morgan) writes:
>In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>>David Franklin wrote:
>>> Firstly, I knocked up a brute force program to do this (took
>>> about 5 mins to write), and got the same answer as Clive Tooth
>>> (97020); the running time was just under 1 second. Which leads
>>> me to wonder about the LCM solution being "much simpler and
>>> faster" as the original interviewer apparently said. When the run
>>> time is 1 second, it's hard to justify spending time speeding it
>>> up (as a one-off problem at any rate).
>>
>>But brute force doesn't scale well, while finding the cycles does.
>>You were just lucky that the period was only 97,020; it could have
>>been much larger if the parameters had been slightly different.
>
>What is the longest possible period? How does one find the answer to
>that without using brute force (nothing occurs to me, but I haven't
>given it much thought).
>
>Alan
I should probably charge a fee for this information but the answer
for 1001 points appears to be:
89*83*79*73*71*67*61*59*53*47*43*41*37*31*29*23*19*17*13*11*7*5*27*16 =
1711349416536879655486838707297798320 ~=
1.711349E+36
As to how you do it, this question gets asked so often, that I wrote a
short and simple C program to calculate the answer - it is basically
brute force with a little cleverness thrown in. It works OK up to degree
about 25000.
Derek Holt.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Hardest ever ECDL solved by INRIA researcher and 195 volunteers
Date: 1 Oct 1999 09:20:20 +0100
Medical Electronics Lab <[EMAIL PROTECTED]> writes:
> Paul Koning wrote:
> > Actually, as of Sept 20, 2000, RSA will have a big advantage...
>
> :-) Not to the owners of the patent.
>
> The patent status on ECC algorithms is not very clear.
> This is definitly a problem, but not an engineering one.
> I would really like to see what the MQV patent will say,
> if it ever issues. If it doesn't issue, so much the
> better!
I had understood that the patents attached to particular optimisations
of ECC, not all of it, and there were reasonable forms that were not
patent encumbered. Am I wrong?
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cryptic manuscript... Help
Date: Fri, 01 Oct 1999 10:33:54 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Also check out Jim reed's Web site; he has a lot of material
> on the Voynich problem, including lots of references.
And Rene Zandbergen's http//voynich.nu
It is very rich, and has many links to serious sites
on the subject. In particular, Prof. Jorge Stolfi's
(do visit it, if anyone is ever going to crack this
code, I'd say Stolfi is the one).
This site below has about 50 high-quality jpegs (but only
black-and-white). They are each about 100k.
http://www.geocities/4oqpcc89/voygal1.htm
Ah yes, "4oqpcc89" is a common "Voynichese word"
in a transliteration system called "frogguy".
In E.V.A. it is "qoteedy". Weird mob, aren't they?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: RSA-512: Weizmann Institute: London Times
Date: 1 Oct 1999 09:27:08 +0100
[EMAIL PROTECTED] writes:
> After an Israeli research institute said it could break Europe's
> banking codes in less than a second, a initiative has been launched
> that could result in unbreakable codes.
If they're named, could you tell us the journalist responsible for
this nonsense? Britain's Murdoch newspaper readers are currently
facing an assault of crypto-nonsense from an especially ignorant and
stupid journalist named Jonathan Ungoed-Thomas, or
"Double-plus-Ungoed" as he is fondly known. I'd be interested to know
if this was him.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: "NP" <[EMAIL PROTECTED]>
Subject: Re: RSA-512: Weizmann Institute: London Times
Date: Fri, 1 Oct 1999 11:18:34 +0100
The article is entitled "No safety in numbers" and is accredited to Ben
Hammersley ([EMAIL PROTECTED]).
This information, and the article, is freely available in the back issue for
29 Sept 1999 at www.the-times.co.uk.
NP
Paul Crowley wrote in message <[EMAIL PROTECTED]>...
>[EMAIL PROTECTED] writes:
>> After an Israeli research institute said it could break Europe's
>> banking codes in less than a second, a initiative has been launched
>> that could result in unbreakable codes.
>
>If they're named, could you tell us the journalist responsible for
>this nonsense? Britain's Murdoch newspaper readers are currently
>facing an assault of crypto-nonsense from an especially ignorant and
>stupid journalist named Jonathan Ungoed-Thomas, or
>"Double-plus-Ungoed" as he is fondly known. I'd be interested to know
>if this was him.
>--
> __
>\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
>/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: drobick <[EMAIL PROTECTED]>
Subject: Re: NEMA, Swiss cipher machine
Date: Mon, 27 Sep 1999 20:00:35 +0200
Frode Weierud wrote:
>
> The Cipher Simulation Group (CSG) has just released a computer
> simulation of the Swiss cipher machine NEMA (NEue MAschine).
> An article describing this machine in great detail will be
> published in the October 1999 issue of Cryptologia.
>
> The NEMA simulator can be downloaded from the following Web sites:
> http://www.blueangel.demon.co.uk/nema/
> and
> http://home.cern.ch/~frode/crypto/simula/nema/index.html
>
> Computer simulations of other cipher machines will be released
> in the near future. A preview of these machines can be seen at:
> http://www.blueangel.demon.co.uk/crypto/
> and
> http://home.cern.ch/~frode/crypto/simula/index.html
>
> Frode
>
> --
> Frode Weierud Phone : +41 22 7674794
> CERN, SL, CH-1211 Geneva 23, Fax : +41 22 7679185
> Switzerland E-mail : [EMAIL PROTECTED]
> WWW : home.cern.ch/~frode
Oh i see 10 Rotor ?!
cool
bye Jo
www.arco.de/~drobick/sas.html
------------------------------
From: [EMAIL PROTECTED]
Subject: security: stream cipher
Date: Fri, 01 Oct 1999 11:14:04 GMT
Can anyone help me:
There is a concept to implement a stream cipher
with LFSR to encode. (f.e. Geffe or Alternating
stop-and-go generator)(with a enough long period)
The output of the PRSG and the Data Stream are
then xored.
The problem is, that the Data Stream consists of
a bitframe in which part of the data (header) can
be known or puzzled.
Therefore an attacker can get part of the key.
Probably a method is to encrypt the header before real
encryption.
//
Is it generally possible to encrypt at stream mode
non random data with a key, which length isn't endless.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: proof
Date: Fri, 01 Oct 1999 11:15:54 GMT
In the hill cipher how many 2x2 matrices are invertible over modulo n?
(where n is a prime number)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: SNAKE Web Page
Date: Fri, 01 Oct 1999 11:34:08 GMT
On Thu, 30 Sep 1999 20:59:41 +0100, Peter Gunn
<[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>>
>> 1) A->B: U, R, V1, V2, V3
>>
>> where V1 = g^X1 mod Q1
>> V2 = g^X2 mod Q2
>> V3 = g^X3 mod Q3
>>
>> Q1 = f(1,P,R)
>> Q2 = f(2,P,R)
>> Q3 = f(3,P,R)
>
>>
>> 2) B->A: S, W1, W2, W3
>>
>> where W1 = g^Y1 mod Q1
>> W2 = g^Y2 mod Q2
>> W3 = g^Y3 mod Q3
>>
>> Q1 = f(1,P,R)
>> Q2 = f(2,P,R)
>> Q3 = f(3,P,R)
>
>>
>> Now A calculates K from:-
>>
>> K = H(U,S,R,P,V1,V2,V3,W1,W2,W3,D1,D2,D3)
>>
>> where D1 = W1^X1 mod Q1
>> D2 = W2^X2 mod Q2
>> D3 = W3^X3 mod Q3
>>
>> and B calculates K from:-
>>
>> K = H(U,S,R,P,V1,V2,V3,W1,W2,W3,E1,E2,E3)
>>
>> where E1 = V1^Y1 mod Q1
>> E2 = V2^Y2 mod Q2
>> E3 = V3^Y3 mod Q3
>>
>> and they both arrive at the same K because Di = Ei, i=1,2,3.
>>
>> 3) A->B: E[K](S)
>>
>> 4) B->A: E[K](R)
>>
>> Now, I can re-describe the attack I posted yesterday as follows:-
>>
>> The adversary impersonates B.
>>
>> Let n be such that g^n < Qi, i=1,2,3.
>
>> The adversary sends S, g^n, g^n, g^n to A in step (2).
>>
>> Now because g^n < Qi, we have g^n = g^n (mod Qi) for i=1,2,3. This
I made a slight typo here, which probably makes the whole thing a bit
more difficult to understand. What I meant to say was:-
Since g^n < Qi, we have Wi = g^n (mod Qi) for i=1,2,3.
(Actually typo is probably the wrong word - is there a word for what
happens when you're thinking one thing but manage to write something
else? :-)
>> means that when A computes Wi^Xi mod Qi it is computing (g^n)^Xi mod
Qi
>> which is the same as (g^X1)^n mod Qi which equals V1^n mod Qi.
>>
>> (I'm using the notation A = B (mod N) for the congruence relationship
>> between A and B, and the notation A mod N to mean A reduced to its
>> least non-negative residue modulo N).
>>
>> The important thing is that we didn't have to guess the Qi in step
(2).
>> We gave A values of Wi = g^n that would work for all moduli. This
means
>> that we can do our guessing of the password/moduli offline as
follows:-
>>
>> First, accept E[K](S) from A in step (3) and abort.
>>
>> Now offline, guess P. From P compute the moduli Qi.
>> From Qi compute V1^n mod Qi. Now compute the key K and check it
>> against E[K](S).
>>
>> Doing this we can recover P.
>>
>> Returning to your restriction on the public values you describe
>> above, I take this to mean that you restrict Vi and Wi such that
>> g^Vi, g^Wi > Z where Z is the smallest possible modulus Qi.
>>
>> To illustrate that this is not enough I'll use your figures from
above.
>> With g=4 I could set n=5 in the attack so that Wi = 1024. This is
less
>> than all 512-bit moduli Qi so the attack will work, and greater than
256
>> so that your proposed restriction will not stop it.
>>
>> I hope this explains things more fully and that it's understandable!
>
>Yes, Im starting to get my head around it.
>
>> Of course, feel free with any questions.
>
>Here is some thinking out loud...
>
>1) Using a larger g, perhaps > SQRT(max modulous) as you suggested
>earlier would seem to go a long way towards stopping this, but would I
>have problems finding a single g that is a valid egenerator for a
table of
>large primes... how do you work that out anyway??
For a prime q of the form 2p+1 then generators are quite common, there
are PHI(q-1) = PHI(2p) = PHI(p) = p-1 of them.
An element g will be a generator modulo q iff g^p = -1 (mod q).
Note that g=4 will never be a generator modulo q because
g^p = (2^2)^p = 2^(2p) = 2^(q-1) = 1 (mod q) by Fermat's Little
Theorem. But this need not be a problem since all you really need is
an element that generates a large prime-order subgroup modulo q.
Since all elements modulo q=2p+1 have order of either 1, 2, p or 2p,
and the only elements with order 1 or 2 are 1 and -1 = q-1 (mod q),
then choosing any other element, apart from 1 and -1, as the basis for
exponentiation will result in a subgroup whose order is a multiple of a
large prime factor. So should be okay.
In the context of SNAKE this means that g should be chosen so as not to
be congruent to 1 or -1 for all primes in the array.
>2) Perhaps I could just ban all values g^n ?? for g==4 this would mean
>I lost 25% of possible values, but it would be pretty easy to implement
>the check (just look at least significant bits). But what else would
this
>affect??
Seems a bit drastic. Not very elegent :-(
>Perhaps another value 4 < g < 256(?) might work and not lose too many
>values?
No. Any other value in that range is still susceptable to the
adversary being able to generate a g^n < Qi.
The reason I suggested choosing a g > SQRT(max[Qi]) is so that the only
g^n < Qi is for n=1, so that you only have to check that
Vi, Wi != g.
>3) Perhaps there is some value in changing the verification procedure??
>Instead of sending the plain values for verfiers R and S, I could
>send E[P](R) and E[P](S)... this would mean that the impersonator
>would have to check each guessed K' value against E[P'](S) and I cant
>immediately see how he could do this??
As I see it, the adversary doesn't make any use of R and S until he is
offline (he can just send any old value for E[P](S) in step (2)). Once
offline, the first thing he does is guess P. This immediately gives
him values for R and S, call them R' and S', which he can plug into the
key derivation function and obtain, as before, a guessed K, call it K',
so that he can now check to see if E[K'](S') is the same as he received
in step (3). It seems highly probable that a wrong guess for P will
give a different result.
>Im also open to ideas ;-)
I'll let you know if I have any :-)
Seriously though, one idea might be to use a "random" g of some kind.
But this is straight from the top of my head, and so I don't know how
this might be done or what weaknesses it may introduce.
Happy protocoling,
Paul(o)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Q: Burrows-Wheeler transform
Date: Fri, 01 Oct 1999 11:58:08 GMT
In article <7t1blf$2vk2$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> In article <7t18at$3vk$[EMAIL PROTECTED]>, Tom St Denis <[EMAIL PROTECTED]>
>wrote:
> >In article <7suncf$pti$[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> >> In article <[EMAIL PROTECTED]>, Mok-Kong Shen
> > <[EMAIL PROTECTED]> wrote:
> >> >While compression is, as far as I am aware, generally regarded
> >> >as orthogonal to encryption, it is nontheless an aid to information
> >> >security, I suppose. Recently I read somewhere a claim that the
> >> >Burrows-Wheeler transform is a better compression technique than
> >> >Huffman or arithmetic encoding. Could some person having knowledge
> >> >and experience with that say whether this is true and whether the
> >> >advantage passes on to encryption? (Could it be that it is slower?)
> >> >
> >> >Thanks in advance.
> >> >
> >> >M. K. Shen
> >> >----------------------
> >> >http://home.t-online.de/home/mok-kong.shen
> >>
> >> For text it is a very good cmpression. However due to the nature
> >> of the BWT I think that it would be hard to write a "one to one" compress
> >> for it. It was the second compression method I looked at and have yet
> >> to make progress making it one to one. So if you use it. Most of the
> >> time a wrong key is guessed in an attacke it will not uncompress.
> >
> >I bet most of the time when you guess the wrong key in your system you don't
> >get ASCII back.
> >
> >Tom
> >
>
> Depends Tom how you do your compression of use a conditional one to one
> compression with encryption when the attacker tries to guess a key it comes
> back as ascii in the character set you limit it too. But like I said you would
> have to be a little older to understand the concept
Ok then run a dictionary attack on three letter worlds. In the domain of
just the plain alphabet you have a 1 in 17576 chance of getting three letter
words. Just look for 'the', 'for', ...etc. If you don't find anything like
that the message is probably not english. You can make it more sophisticated
and look for ' the ' which is 1 in 11,881,376 ...etc
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (jerome)
Subject: Re: msg for Dave Scott
Reply-To: [EMAIL PROTECTED]
Date: Thu, 30 Sep 1999 21:27:58 GMT
as far as i know, there isnt a predefined size for a block, so 1 byte
will do, even if it is unsual.
so if you have only one block (1 byte in this case), your key is as
long as your message. so with the random key, a caesar cypher has the
same carasteric as an one time pad, then is unconditionnaly secure.
it was an silly example that a weak cypher easily becomes
unconditionnaly secure when you limit the amount of cypher
texts.
On Thu, 30 Sep 1999 14:03:10 -0600, Jerry Coffin wrote:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>says...
>
>[ ...]
>
>> btw: with only 1 block, even a caesar cypher is unconditionaly secure
>> with a random key.
>Hmm...either you and I have somewhat different understandings of what
>a Ceaser Cipher IS, or else this doesn't make a lot of sense. At
>least as I understand it, a Ceaser Cipher is basically not a block
>cipher at all. It's a stream cipher that works on character at a
>time. In a Ceaser Cipher, the "key" is an offset in the alphabet, and
>for each character, you substitute the character at that offset from
>the original to get the encrypted text. E.g. ROT13 is essentially a
>Ceasar Cipher with a fixed key of 13. If you took ROT13 code and
>allowed the user to enter a different value instead of 13, you'd have
>a generalized version of a Ceasar Cipher. As I recall, in the
>original form, the key was also fixed, but at 3 instead of 13.
>
>In any case, unless you define a block as a character, there's no real
>way to talk about a number of blocks WRT a Ceasar Cipher. Using a
>known-plaintext attack, you can break a Ceasar Cipher with only one
>character. Using a ciphertext-only attack, you have to collect enough
>to gather a little bit in the way of statistics, but we're looking at
>a pretty small number in most cases -- you stand a chance as soon as
>you see the same character twice (it's most likely a space or an 'e',
>depending on whether they've taken the spaces out of the plaintext
>before encryption). With only one repeated character, you might well
>be wrong, but it doesn't take very many more to reduce the chances of
>being wrong to nearly nonexistent.
>
>--
> Later,
> Jerry.
>
>The universe is a figment of its own imagination.
------------------------------
From: "Boris Kolar" <[EMAIL PROTECTED]>
Subject: Re: Example of a one way function?
Date: Fri, 1 Oct 1999 13:41:46 +0200
Tim Tyler <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Boris Kolar <[EMAIL PROTECTED]> wrote:
> : Roger Carbol <[EMAIL PROTECTED]> wrote in message
> :> I. Michael Mandelberg <[EMAIL PROTECTED]> wrote:
>
> :> > Can someone point me to a one-way-function that is typically used
> :> > for encryption?
> :>
> :> Multiplication.
>
> : Of course multiplication is a one-way function, but It's not a very
> : conveniant one.
>
> Multiplication is a one-way function? I'd have thought it was
> generally eminently reversible.
Multiplication (in the field of integers) is believed to be one-way:
1) The easy way: multiply two integers (preferably primes)
2) The hard way (invertion): given integer x find integers (a,b), such
that a*b=x
>
> I think you need to invoke complex numbers, or modulo arithmetic,
> or *something* if you want to claim multiplication as a one-way
> function.
No. Multiplication of complex numbers is easily invertible.
> --
> __________
> |im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
>
> 29A - the hexadecimal of the Beast.
------------------------------
** 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
******************************
