Cryptography-Digest Digest #20, Volume #12 Tue, 13 Jun 00 15:13:00 EDT
Contents:
Re: SBOX finder client (Simon Johnson)
GeekPress: Will Cyber Criminals Run the World? ([EMAIL PROTECTED])
McTER 2 (manual crypt) (=?ISO-8859-1?Q?Jacques_Th=E9riault?=)
Re: Updated: Evidence Eliminator Dis-Information Center ([EMAIL PROTECTED])
Re: DPmax of Feistel Construction (Mark Wooding)
Re: DPmax of Feistel Construction (tomstd)
Re: Random sboxes... real info (Tim Tyler)
Re: CRC Programming Help... Please!! (Joseph Reuter)
Re: DPmax of Feistel Construction (Mark Wooding)
Re: DPmax of Feistel Construction (tomstd)
Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher)) (csybrandy)
Re: Random sboxes... real info (tomstd)
Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher)) (tomstd)
Re: Finding prime numbers (Bryan Olson)
Re: Finding prime numbers (AllanW)
----------------------------------------------------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: SBOX finder client
Date: Tue, 13 Jun 2000 16:57:32 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, Runu Knips
> <[EMAIL PROTECTED]> wrote:
> >Runu Knips wrote:
> >> tomstd wrote:
> >> > Sorry there is no other ports at this time (I know somebody
> is
> >> > gonna comment). However the FULL source code is given and
> it's
> >> > a very dirty hack of SBOXGEN anyways..
> >>
> >> See www.wxwindows.org. LGPL GUI for Windows (16 and 32 bit) +
> >> Unix (GTK+ and Motif/Lesstif), other systems in development
> >> (early BETA for MacOS). Currently still in BETA (if you want
> to
> >> use the 2.x version, which is far cooler than 1.x. 1.x is
> already
> >> final, frozen, done, for Windows/OS2/Unix etc.), but fairly
> >> useable.
> >>
> >> At the moment, I've even stopped working at my cipher (whirl)
> >> and started to write a little program with that lib.
> FASCINATING !
> >> ;-)))
> >
> >Ooops, forget it. Such kind of program doesn't need to be
> >graphic on systems other than Windows anyway...
> >
>
> I am working on optimizing my code for the task. Last night I
> brought the code from 6000sboxes/sec to 13000sboxes/sec. I just
> have to check to make sure it's still doing the same test :)
>
> Tom
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion
Network *
> The fastest and easiest way to search and participate in Usenet -
Free!
>
>
What a clever idea :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: GeekPress: Will Cyber Criminals Run the World?
Date: Tue, 13 Jun 2000 17:21:26 GMT
The article below was posted to GeekPress
(http://www.geekpress.com) earlier today. Enjoy!
************************************************************
Will Cyber Criminals Run the World?
http://www.time.com/time/magazine/articles/0,3266,47159,00.html
Summary:
Science fiction writer Bruce Sterling argues that the sort
of "cryptoanarchy" advocated by cypherpunks such as Tim May
is unviable. He faults both the cypherpunks and the
federal government for portraying cryptography as a more
powerful tool (for good or evil, depending on one's POV)
than it really is.
Commentary:
An interesting counterpoint to the ideas in Tim May's
Cyphernomicon
(http://www.oberlin.edu/~brchkind/cyphernomicon/cyphernomic
on.contents.html).
Post your comments on GeekPress:
http://www.geekpress.com/cgi-bin/comments/read.pl?id=13-6-2000-8-15-33&datetime=Tue+Jun+13+08:15:33+2000+PDT
************************************************************
More great tech news stories are available on GeekPress
at http://www.geekpress.com throughout each day!
************************************************************
Recent Stories:
-=- Livermore simulates explosion at quantum level
http://www.geekpress.com/cgi-bin/comments/read.pl?id=13-6-2000-9-28-55&datetime=Tue+Jun+13+09:28:55+2000+PDT
-=- Navy sends 250 sensitive e-mails to schoolgirl
http://www.geekpress.com/cgi-bin/comments/read.pl?id=13-6-2000-8-31-59&datetime=Tue+Jun+13+08:31:59+2000+PDT
-=- Trappin' Your Cheatin' Heart
http://www.geekpress.com/cgi-bin/comments/read.pl?id=13-6-2000-7-46-03&datetime=Tue+Jun+13+07:46:03+2000+PDT
-=- Systems of the Future
http://www.geekpress.com/cgi-bin/comments/read.pl?id=13-6-2000-0-29-54&datetime=Tue+Jun+13+00:29:54+2000+PDT
-=- Why Free Net Phone Calls Keep Telcos Up At Night
http://www.geekpress.com/cgi-bin/comments/read.pl?id=12-6-2000-23-45-09&datetime=Mon+Jun+12+23:45:09+2000+PDT
-=- Transmeta to hit 1 GHz by year-end
http://www.geekpress.com/cgi-bin/comments/read.pl?id=12-6-2000-21-48-07&datetime=Mon+Jun+12+21:48:07+2000+PDT
************************************************************
-- Diana Hsieh
GeekPress, Tech News Sifted and Summarized
http://www.geekpress.com
------------------------------
Subject: McTER 2 (manual crypt)
From: [EMAIL PROTECTED] (=?ISO-8859-1?Q?Jacques_Th=E9riault?=)
Date: Tue, 13 Jun 2000 17:22:19 GMT
MCTER 2
========================================================================
==========
1111
IDX 5555555566666666667777777777888888888899999999990000
2345678901234567890123456789012345678901234567890123
----------------------------------------------------
IDX 111111111122222222223333333333444444444455
0123456789012345678901234567890123456789012345678901
ALFA ABCDEFGHIJKLMNOPQRSTUVWXYZ@!"#$%&'()*+,-./0123456789
Key1 FIRSTKEYFIRSTKEYFIRSTKEYFIRSTKEYFIRSTKEYFIRSTKEYFIRS
Key2 SECONDKEYSECONDKEYSECONDKEYSECONDKEYSECONDKEYSECONDK
Kmix X)C(O!/R4U/J0NUCL1@6R/G'6I7'EQ(T!3OE/DJ5NY9VM.6W/K$G
Mix0 -13H!I&XT*I21EVOG!YN.M2+@3D6X#1EA.J*IP9VZ9FRI'WONVM2
Mix1 N$L($77(5D8GXBN@XT34T08NQ7%2F(9#0PS@V5-#@SP(#20DE4R4
Mix2 54ASRLFX@2JO!V0V("UKU)AVD7@DO&@GV0K*TW9%FZ4E*UO&7L-B
PTXT PLAINTEXTONEPTEXTTWOPTEXTTHREEPTEXTFOURPTEXTFIVEPTEX
CTXT X)LII!G".JUYN/HSYO)SC2CF,NMMXS.CP"5PC+DX85&FSUZ-QYIS
========================================================================
==========
The message is encrypted by chunk of 52 characters. So the key can be
52 character
long. If it is shorter it is reused until all the 52 positions are
filled.
========================================================================
==========
All arrays are 52 elements of 1 character, array elements starts at 0
ALFA - is the array with the letters "A-Z" and "Space - 9" in
ascending ascii
characters.
IDX - is the index of each characters of ALFA
Set up array key1 with the first key, repeating the key if necessary
Set up array key2 with the second key, repeating the key if necessary
Ex: key1(0) = 5 5 is the index of 'F' of key1 in ALFA
Ex: key2(0) = 18 18 is the index of 'S' of key2 in ALFA
Once that is set up you add respective array elements of key1() and
key2() to
produce the array kmix(). All the additions are Modulo 52
Set tmp = 0
tmp = ( tmp + key1(0) + key2(0) ) MOD 52
kmix(0) = tmp
and you repeat that for the 52 elements of key1() and key2()
Repeat with chunk of 52 characters of plaintext, pad with blanks if
less than 52
Example of a typical round. There is three of them
FOR i = 0 to 51 ' mix all the 52 elements of the key
c1 = lookup index character kmix(i) in ALFA
c2 = lookup index character kmix(c1) in ALFA
iv = (iv + c2) MOD 52
mix0(i) = ALFA(iv)
NEXT i
UNTIL there is no more chunk of plaintext
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *
This is a system designed to be used manually. Using a computer or a
calculator
facilitate the coding enormously, but the fact remains that you can
operate
this with brain power only...Or maybe make a program on a HP41 or some
similar
calculators.
This is my second attempt to design a cypher algorithm with the
possibility to
use it manually. The first one Mcter was posted earlier this year on
this newsgroup.
The design was similar to this one, but more simple in design.
Mcter 2 uses 2 keys and 3 rounds for each chunk of 52 characters of
plaintext.
I've used 2 keys and try to mix them in a way that the keys are not
leaked or cannot
be easily guessed.
At 52 character there is a little bit more than 5.5 bits of entropy in
the key.
So the combined keys are 52 x 5.5, or 286 bits. or 2^286 or 1.24E+86.
The mixing of the keys and the 3 rounds uses a feedback mechanism where
the last
character calculated is re-used in the next calculation.
The first round is discarted to prevent anything before it leaking into
the cypher text
calculation.
In the cyphertext calculation, each character is calculated
individually, nothing is
carried to the preceding or following characters. The plaintext doesn't
leak anything
in the subsequent rounds. The cyphertext depends only on mix1 and mix2
I would like to get comments on this algorithm and how secure it is.
Recommendations are welcome to improve or change the algorithm as you
wish.
Jacques Th�riault
[EMAIL PROTECTED]
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * *
Following is a Basic program to help you test if you want
DIM 1 look$(255)
DIM k1(255), k2(255), m0(255),m1(255),m2(255), pt1(255), PT2(255)
look$ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ !"+CHR$(34) +
"#$%&'()*+,-./0123456789"
k1$ = "FIRSTKEY": k2$ = "SECONDKEY"
pt1$ = "PLAINTEXTONEPTEXTTWOPTEXDPLAINTEXTONEPTEXTTWOPTEXD"
JMX = LEN(look$)-1 ' num of elements - 1
WHILE LEN(k1$) < (jmx+1) ' fill key 1
k1$ = k1$ + k1$
WEND
k1$ = LEFT$(k1$,jmx+1) 'size it
WHILE LEN(k2$) < (jmx+1) 'fill key 2
k2$ = k2$ + k2$
WEND
k1$ = LEFT$(k1$,jmx+1) 'size it
WHILE LEN(pt1$) < (jmx+1)
pt1$ = pt1$ + pt1$
WEND
pt1$ = LEFT$(pt1$,jmx+1)
CLS
PRINT "ALFA ";
FOR j = 0 TO JMX
PRINT MID$(look$,j+1,1);
fp1 = INSTR(1,look$, MID$(k1$,j+1,1)) -1
fp2 = INSTR(1,look$, MID$(k2$,j+1,1)) -1
fp3 = INSTR(1,look$, MID$(pt1$,j+1,1)) -1
fp4 = INSTR(1,look$, MID$(pt2$,j+1,1)) -1
k1(j) = fp1 :k2(j) = fp2 :pt1(j) = fp3 :pt2(j) = fp4
look$(j) = MID$(look$,j+1,1)
NEXT j
PRINT :PRINT "Key1 ";
FOR j = 0 TO JMX
fpx = INSTR(1,look$, MID$(k1$,j+1,1)) -1: PRINT look$(fpx);
NEXT j
PRINT: PRINT "Key2 ";
FOR j = 0 TO JMX
fpx = INSTR(1,look$, MID$(k2$,j+1,1)) -1: PRINT look$(fpx);
NEXT j
PRINT: PRINT "Kmix ";
kmx% = 0
FOR j = 0 TO JMX
m0(j) =( k1(j) + k2(j) + kmx%) MOD (JMX+1): m2(j) = m0(j): kmx% =
m0(j): PRINT look$(m0(j));
NEXT j
iv = kmx% ' Initial value
IMPORTANT
rem CONTINUE here if you have more Plaintext to code
MORE:
PRINT: PRINT "Mix0 ";
FOR j = 0 TO JMX
c1 = m0( j): c2 = m0( c1 ): iv = (c2 + iv) MOD (JMX+1): m0(j) = iv:
PRINT look$(m0(j));
NEXT j
PRINT: PRINT "Mix1 ";
FOR j = 0 TO JMX
c1 = m0( j): c2 = m0( c1 ): iv = (c2 + iv) MOD (JMX+1): m1(j) = iv:
m0(j) = iv
PRINT look$(m1(j));
NEXT j
PRINT: PRINT "Mix2 ";
FOR j = 0 TO JMX
c1 = m0( j): c2 = m0( c1 ): iv = (c2 + iv) MOD (JMX+1): m0(j) = iv:
m2(j) = iv
PRINT look$(m2(j));
NEXT j
PRINT: PRINT "Ptex ";
FOR j = 0 TO JMX
PRINT look$(pt1(j));spx$;
NEXT j
PRINT: PRINT "Ctex ";
TEXT _monaco,9,0
FOR j = 0 TO JMX
c1 = m1(j): c2 = m2(j): c3 = pt1(j): ct = (c1 + c2 + c3 ) MOD
(JMX+1): PRINT look$(ct);
NEXT j
PRINT
rem NOTE: If there is more plaintext then goto the label 'MORE:' above
rem continue with the 'iv' value last calculated
============== END OF BASIC LISTING =============
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Updated: Evidence Eliminator Dis-Information Center
Date: Tue, 13 Jun 2000 17:26:44 +0100
On 13 Jun 2000 12:20:58 GMT, [EMAIL PROTECTED] (Richard Herring)
wrote:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
>
>> Let me remind you of one thing about cops. Do you know who it was who
>> turned over all the Jewish children in France to the Nazis for
>> extermination?
>
>I claim Godwin's Law. You lose. Nwo go away.
"Godwin's Law of Nazi Analogies: As an online discussion grows longer,
the probability of a comparison involving Nazis or Hitler approaches
one."
Well, I ignored this the first time you posted it, , but since you're
an insistent little nazis, I'll take it up:
It seems we have a holocaust deniers here. A rather trendy viewpoint
of our amoral/immoral times. A history revisionist.
The police in Europe, especially in France, fully helped the nazis
with the rounding up and extermination of the Jews. Matter of fact,
France is the only country which still has not admitted to the fact.
And with that, I won't indulge in further discussion with
anti-semitic filth such as yourself.
PLONK!
- Thistle -
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DPmax of Feistel Construction
Date: 13 Jun 2000 17:24:58 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> Nope I mix in round constants... check this out
>
> for (r = 0; r < z; ) {
> a ^= sbox[0][b ^ ++r]; b ^= sbox[0][a ^ ++r]; }
>
> So each round is slightly different then the last.
I don't think that's enough to make the rounds statistically
independent. I suspect that the critical point is that the round
constants are known.
-- [mdw]
------------------------------
Subject: Re: DPmax of Feistel Construction
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 13 Jun 2000 10:38:04 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> Nope I mix in round constants... check this out
>>
>> for (r = 0; r < z; ) {
>> a ^= sbox[0][b ^ ++r]; b ^= sbox[0][a ^ ++r]; }
>>
>> So each round is slightly different then the last.
>
>I don't think that's enough to make the rounds statistically
>independent. I suspect that the critical point is that the
round
>constants are known.
So you are hinting at the fact that the various differentials
are key depenedant and not structural?
I think it's still interesting that differential exist (even if
unknown) after 128+ rounds of the structure.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Reply-To: [EMAIL PROTECTED]
Date: Tue, 13 Jun 2000 17:33:32 GMT
tomstd <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>tomstd <[EMAIL PROTECTED]> wrote:
:>: There is alot of merit in the idea of keyed substitution boxes,
:>: however alot of care has to go into their construction. Large
:>: random sboxes are rarely secure which is why they have to be
:>: specifically constructed. For example look at a block 64-bit
:>: cipher, only a handful of the 2^64! possible 64-bit
:>: substitutions boxes are possible, but out of all of the
:>: possible tables very few are weak. Try to think of the block cipher
:>: has a big sbox and it will help you design smaller tables.
:>
:>There seems to be some irony here. AFAIK, most folks agree
:> that a block cypher should attempt to emulate a random permutation.
:>
:>Some random permutations are weak, but the chances of any of
:>them coinciding with one of your keys is considered extremely remote.
:>
:>So, following the advice of looking at a block cypher and
:>thinking of it as a large s-box (in the hope of this helping you design
:>smaller tables) apparently leads to the idea that smaller s-boxes should
:>be constructed
:>as random permutations...
: No you failed to see my point.
: Let's take RC5 with a 128 bit key. There are about 2^128
: possible permutations right?
Y
: Well those 2^128 permutations out of the entire (2^64)!
: permutations are strong with respect to diff and linear
: analysis.
Not compared to a random permutation. Or at least, they shouldn't be -
since a random permutation is what block cyphers are generally and
widely considered to be trying to emulate.
: They are hardly any random permutation, the
: permutations are *dictated* by the algorithm itself.
Indeed. A potential source of weakness. If only the cypher could more
closely approximate a random permutation, the anayst would be completely
lost.
: Remember that 2^128 is only a TINY fraction of (2^64)!.
Of course.
: That's why constructions like that are more favourable. We can
: tell to some degree what permutations constructed using a
: particular structure will behave like.
...and we hope they behave like random permutations. Deviations from
random permutations are regarded with suspicion. The cypher is not
approaching the ideal - and this is a potential source of worry.
We seem to have a philosophical difference here. As far as I know,
it is widely believed that block cyphers should emulate the ideal of
simulating a random permutation, with each key.
For example, it was the second criteria listed for AES candidate security:
``Algorithms will be judged on the following factors:
i) Actual security of the algorithm compared to other submitted
algorithms (at the same key and block size).
ii) The extent to which the algorithm output is indistinguishable from a
random permutation on the input block.''
[from http://csrc.nist.gov/encryption/aes/round2/aes_9909.htm]
It might be objected that this set includes the identity transformation
- but as you say, a 2^128 keyspace has such a small chance of hitting on
this (or other weak transformations) nobody wastes any sleep over it.
Now *you* seem to think a block cypher should not emulate a random
permutation - but should somehow concentrate on the strong
transformations. Yet it seems to me that a 128-bit random permutation is
already likely to be /fantastically/ strong.
Further there's no known practical way of weeding out those
transformations which are (say) more linear than average. You can't test
a 128-bit permutation - because it's much too big. You can't combine
smaller non-linear functions and expect the result to be more non-linear
than average - because combining non-linear functions can sometimes
produce linearity.
I don't think anybody does this. AFAIK, everybody else is trying to
simulate random permutation, and nobody checks to see if the result is
the identity fuinction - or some other weak construct - bacause the
chances of this happening if a random permutation is approached are so
utterly miniscule.
Your view on this subject appears to me to be bizarre and unorthodox.
Can you think of anyone else who explicitly shares your POV?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Be good, do good.
------------------------------
From: Joseph Reuter <[EMAIL PROTECTED]>
Subject: Re: CRC Programming Help... Please!!
Date: Tue, 13 Jun 2000 11:03:26 -0700
gKw-X wrote:
>
> hey guys!
>
> i have some questions regarding crc computation... an answer to any
> extent to these qs would be greatly appreciated :)
>
> if one program uses certain variables to create the crcs, and you
> can't see what they are directly, is there any way to determine the
> variables that go into it by somehow 'reverse engineering' the crc
> outputs for different files? (so that you can then support the outputs
> of other programs)
>
[much confusion about CRC snipped]
A Cyclic Redundancy Checksum is not a cryptographic hash. It's not
a hash at all. It is an error-detecting code, usually chosen because
it guarantees to detect any burst of errors whose length is less
than the length of the checksum. The code is generated by a process
of polynomial division, where the polynomial coefficients are integers
modulo 2.
The "variables" are the coefficients of the generator polynomial.
Only a small fraction of the polynomials produce an error detecting
code with the above properties.
Since polynomial division is linear, the worst possible requirement
to reconstruct the randomly-selected coefficients of a generator
polynomial would be one message+checksum for each bit in the
checksum length.
Maybe we need to get this into a FAQ somewhere:
A Cyclic Redundancy Checksum (CRC) is linear, and will never be
cryptographically secure!
Joe
--
Joseph A. Reuter, Wizard-in-Training [EMAIL PROTECTED]
"Olorin I was in my youth in the West that is forgotten."--Tolkien
You can't win, you can't break even, and it's the only game in town.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: DPmax of Feistel Construction
Date: 13 Jun 2000 18:02:25 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> So you are hinting at the fact that the various differentials
> are key depenedant and not structural?
No. Since the `keys' are known, we can take them into account when
analysing the entire construction. Usually the `keys' are unknown and
random, so the best we can do is to assume that the rounds are separate
and independent.
-- [mdw]
------------------------------
Subject: Re: DPmax of Feistel Construction
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 13 Jun 2000 11:33:48 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> So you are hinting at the fact that the various differentials
>> are key depenedant and not structural?
>
>No. Since the `keys' are known, we can take them into account
when
>analysing the entire construction. Usually the `keys' are
unknown and
>random, so the best we can do is to assume that the rounds are
separate
>and independent.
So how to do you find the best diff? Find the highest entry in
the xor table and reise it to power of the rounds used? So in
the four round construction we have
(2^-6)^4 = 2^-24 which means there is no diff for the entire
construction?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: csybrandy <[EMAIL PROTECTED]>
Subject: Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher))
Date: Tue, 13 Jun 2000 14:27:25 -0400
Reply-To: [EMAIL PROTECTED]
Well, I think this is a good time to retire from the encryption
algorithm design market until I learn some more. Thanks to everyone for
not letting my ego get too big :-)
Too bad it's a mute point that I made it fast.
csybrandy
<snip>
------------------------------
Subject: Re: Random sboxes... real info
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 13 Jun 2000 11:40:09 -0700
You're not seeing the big picture. By making a cipher more
structured (i.e designed by an algorithm) you can actually make
the output *more* random.
Consider differential cryptanalysis. The whole point of this
attack is to distinguish the permutation from random. If you
pick a random 128x128 sbox for example (suppose it could be
done) and there was a differential that needed only 16
plaintexts to identify... well then I could find it much quicker.
However if you make a 128x128 sbox which is dependent solely on
the userkey and is made from a structured algorithm, you can
hopefully resist these statistical attacks.
The whole point of showing off the random sboxes is to show that
random permutations are hardly ideal. That's why we have block
ciphers designed to be resistant to these attacks. Each block
ciphers keyspace defines a subset of all permutations that are
resistant to these attacks. They are hardly random, just
independent, which is what makes the keyspace appear random.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher))
From: tomstd <[EMAIL PROTECTED]>
Date: Tue, 13 Jun 2000 11:43:28 -0700
In article <[EMAIL PROTECTED]>, csybrandy
<[EMAIL PROTECTED]> wrote:
>Well, I think this is a good time to retire from the encryption
>algorithm design market until I learn some more. Thanks to
everyone for
>not letting my ego get too big :-)
>
>Too bad it's a mute point that I made it fast.
Aye speed isn't everything when it's insecure my dear ol'friend.
TC1 was quick .... and broken.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Tue, 13 Jun 2000 18:49:17 GMT
I wrote:
> Since we have algorithms that can find
> the almost-certainly next prime in polynomial time, a
> next-prime oracle could not reduce the time from
> super-polynomial to polynomial.
I didn't write that as clearly as I should.
Our best factoring algorithms are currently super-polynomial
time. Now suppose we have a next-prime oracle; given a
prime it returns the next prime in constant time. Could the
oracle be the key to reducing the time to factor to
polynomial?
No it could not. If we had a polynomial time factoring
algorithm that uses the oracle, we could always replace the
oracle with our current next-prime method. Our current
next-prime algorithm is polynomial time. Replacing all
the calls to the oracle in the p-time factoring algorithm
with calls to the p-time next-prime algorithm, would at
worst result in a run time proportional to the product of
the two polynomials, which is also a polynomial.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Tue, 13 Jun 2000 18:49:18 GMT
I wrote:
>> Suppose I had an algorithm so that, given a prime number P(n),
>> I could find the next prime number P(n+1) extremely quickly.
>> Let's say it was as quick as four or five integer additions.
>> (I don't actually have such an algorithm, but let's say I did.)
>>
>> I'm guessing that an algorithm like this would make brute-force
>> attacks on private keys easier. Given a public key it would be
>> possible to derive the private key in a practical amount of
>> time, unless people started using much bigger keys than they
>> normally do now. And of course once the attacker had the
>> private key they could use it any way they wished.
In article <eAjr63P1$GA.310@cpmsnbbsa07>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> Well it would speed up some methods, but I don't think it
> would provide an increase over the current best. Assuming a
> 1024-bit key with factors known to be 512-bits each, there
> should be ~10^150 primes of value less than 2^513, subtract
> the ones that are smaller than 2^512, we can estimate the
> number of primes at still around 10^150, the actual value
> being 255*2^512/261632. So even if the time was reduced to 1
> clock for the prime finding, trial division would take
> approximately 2^200+ attempts, that would still be 10^43
> years on a 1 GHz computer. I'm sorry but it's still not
> enough alone.
Thank you, Joe. It looks like you've thought about this before.
The strength of a public-key/private-key system relies on the
fact that the two keys work together, and yet you can't easily
derive one key from the other one. I've often read that this
in turn relies on the fact that factoring huge prime numbers
is a slow process.
What made me wonder is the phenomenal rate at which computer
storage is growing. 20 years ago consumer disk drives weren't
much larger than 20-megabytes, that's about 10^7. Today we
can buy disks nearly 100-gigabytes, 10^11. That's a factor of
10 every 5 years. RAID and other technology must give
industrial users considerably more storage than that. DoD
budget ought to make 10^15 bytes of storage a practical
reality. (Anyone know the name for 1000 terabytes?) And if
DoD was to have a 1000-machine network, each equipped with a
10^15 RAID, the total disk space would be 10^18
(1,000,000 terabytes).
I think you can see where I'm going with this. If we can
calculate all of the large primes in advance and store them
on mass media, then calculating the next prime won't be an
issue. We're probably not there yet. If we start at 10^18
and jump by 10 every 5 years, it ought to take over 130
years.
But there's an awful lot of "if's" in that paragraph. Any
one of those assumptions could be understated, making the
real timeframe much less. With all the secrets in Washington,
it could even be happening today. Who would know?
> A much more important goal would be to reduce
> the necessary number of primes, or simply find a better way
> than primes.
I suppose that's true. But it's unlikely on it's face. Finding
prime factors without knowing the primes would seem to be like
guessing how to spell a word without knowing the alphabet.
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
