Cryptography-Digest Digest #909, Volume #8 Fri, 15 Jan 99 08:13:02 EST
Contents:
Rabin/Williams/Koyama .. and Flannery?
Re: UK TV programme on Enigma ("NewsUser.2436")
Re: Visual Basic Cipher (Jessica Anderson)
Re: Help me with this crypto ! (Jessica Anderson)
BASIC RC4 (Matthias Bruestle)
PKCS11 Implementation Problems ([EMAIL PROTECTED])
Re: Cayley-Purser algorithm? ([EMAIL PROTECTED])
Re: Some Non-Random DES Characteristics (Matthew Skala)
Re: On the Generation of Pseudo-OTP (fungus)
Re: What is left to invent? (R. Knauer)
Re: Practical True Random Number Generator (R. Knauer)
Re: New Twofish Source Code Available (Bruce Schneier)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Random numbers in C: Some suggestions. (Bernhard Treutwein)
Re: On the Generation of Pseudo-OTP (R. Knauer)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] ()
Subject: Rabin/Williams/Koyama .. and Flannery?
Date: 15 Jan 99 05:13:44 GMT
I must withdraw some of my earlier comments on the announcement that a
young woman of 16 from Ireland has developed a public key algorithm that
is much faster than RSA.
I had thought that this was too good to be true, and that almost certainly
she had made some mistake in matrix algebra, thereby overlooking a trivial
solution.
However, after digging out my trusty copy of Applied Cryptography, it
seems that algorithms which, unlike RSA, do not require large
exponentiations of the enciphered block _already exist_ ... and,
furthermore, unlike RSA, they are provably as secure as factoring! Thus, I
was, apparently, quite mistaken in thinking that this announcement was
just too good to be true.
Of course, since repeated squarings provide a very fast way of taking a
number to a high power - and determining if a number is a quadratic
residue or not of some prime is, perhaps, more difficult - RSA has the
advantage of being simpler to understand. Is it because the RSA patent
covers them, or is it for other reasons, that the Rabin or Williams
methods - or the Koyama 2-dimensional method, which may be the most
similar to this new method - are not widely used?
John Savard
------------------------------
From: "NewsUser.2436" <[EMAIL PROTECTED]>
Subject: Re: UK TV programme on Enigma
Date: Thu, 14 Jan 1999 19:21:51 +0000
Reply-To: "NewsUser.2436" <[EMAIL PROTECTED]>
In article <[EMAIL PROTECTED]>, David Hamilton
<[EMAIL PROTECTED]> writes
>
>UK TV Channel 4 is showing 'Station X' on Tuesday 19th January at 9:00pm.
>It's about breaking the Enigma code which was done, according to the trailer,
>by chess champions and crossword fanatics.
You might also find the book to accompany the series of interest:
Station X, The codebreakers of Bletchley Park.
by Michael Smith,
Pub. 1998 by Channel 4 books (an imprint of Macmillan books)
ISBN 0-7522-2189-2 (Hbk, UKP 14.99)
p.s.
Just a happy reader - having no connection with Channel4, the author, or
the publishers ;-) but looking forward to the series.
--
Paul newsuser.2436 @ G 4 I K J .demon.co.uk
Never argue with a fool, he may be doing the same.
------------------------------
From: Jessica Anderson <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Cipher
Date: Thu, 14 Jan 1999 22:55:13 -0800
Yes. Well, I guess it depends on how secure/fast you want it. With my limited
knowledge, I've made some pretty hefty byte/bitwise encryption schemes. None
as sophisticated as having asymetrical keys or even large primes. Ive found
ways of doing hefty things with xors but those are relatively insecure.
If someone could maybe help me find a way to generate large primes in vb
using eulers method maybe then we could start a sci.crypt.vb or just have a
thread in here for VB stuff. I have to believe that there are more than two
people trying.
Best of luck to you and any questions can be emailed to me at
[EMAIL PROTECTED]
-Jess
CYFer wrote:
> Is it possible to make a secure encryption system using VB, without using
> any outside ActiveX?
------------------------------
From: Jessica Anderson <[EMAIL PROTECTED]>
Subject: Re: Help me with this crypto !
Date: Thu, 14 Jan 1999 23:03:08 -0800
So essentially, you are trying to reverse engineer it... to make a new one.
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> Nicol So <[EMAIL PROTECTED]> wrote:
> > Actually, I've seen a device that fits your description. It's a token
> > for challenge/response authentication. When you use it for remote
> > login, the remote system presents you with a "challenge" in the form of
> > an 8(?)-digit number, which you'd enter into the token for the proper
> > response.
> >
> > Are you trying to reverse engineer the box?
> >
> > Nicol
> >
>
> No, i will write a program that does the same as the box, because the
> box is a really slow and i hate it.
>
> >
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Matthias Bruestle)
Subject: BASIC RC4
Date: Thu, 14 Jan 1999 15:48:59 GMT
Mahlzeit
Because of the outstanding success of my SAFER and RC4 implementations
for PDP-11 I post here and now my implementation of RC4 in Basic for
pocket computers.
The timings and sizes for my Sharp PC-1403 (bought around 1990):
Keysetup without RC4-cycles: 106s
Keysetup with RC4-cycles: 181s
RC4: 0.3s
Program: ca. 530 Bytes
Data: ca. 2160 Bytes
For testing against test vectors remove REM from line 1345.
Mahlzeit
endergone Zwiebeltuete
1000 REM *RC4-PROGRAMM*
1010 PRINT "*RC4*"
1020 INPUT "Key: ";KY$
1030 GOSUB 1200
1050 B=256
1060 INPUT "Input Byte: ";B
1070 IF ((B<0) OR (B>255) THEN CLEAR:PRINT "Done.":END
1080 GOSUB 1400
1090 B=B XOR K
1100 PRINT "Output Byte: ";B
1110 GOTO 1050
1200 REM VAR: KEY: KY$, S-BOX: SB(), TMP: ZC,ZI,ZJ,ZK$
1210 ZC=0:ZJ=0
1220 DIM SB(255)
1230 FOR ZI=0 TO 255
1240 SB(ZI)=ZI
1250 NEXT ZI
1260 FOR ZI=0 TO 255
1270 ZK$=MID$(KY$,ZC+1,1)
1280 ZJ=(ZJ+SB(ZI)+ASC ZK$) AND 255
1290 ZT=SB(ZI):SB(ZI)=SB(ZJ):SB(ZJ)=ZT
1300 ZC=ZC+1
1310 IF (ZC=LEN KY$) THEN LET ZC=0
1320 NEXT ZI
1330 KY$="XXXXXXXXXXXXXXXXXXXXXXXXX"
1340 I=0:J=0
1345 REM RETURN
1350 FOR ZI=0 TO 255
1360 GOSUB 1400
1370 NEXT ZI
1380 RETURN
1400 REM VAR: I: I, J: J, S-BOX: SB(), TMP: ZT
1410 I=(I+1) AND 255
1420 J=(J+SB(I)) AND 255
1430 ZT=SB(I):SB(I)=SB(J):SB(J)=ZT
1440 ZT=(SB(I)+SB(J)) AND 255
1450 K=SB(ZT)
1460 RETURN
--
PGP: SIG:C379A331 ENC:F47FA83D I LOVE MY PDP-11/34A, M70 and MicroVAXII!
--
Nuclear weapons make great concrete overcoat removers with fast butter!
------------------------------
From: [EMAIL PROTECTED]
Subject: PKCS11 Implementation Problems
Date: Fri, 15 Jan 1999 07:52:26 GMT
Hi, Could anyone give me any advices?
I have implemented a PKCS#11 module according to the PKCS#11 Spec. and
Netscape comments. Adding it into Communicator by Security dialog.
Consequently,nothing was added.
I wrote a test program: LoadLibrary, then GetProcAddress of
C_GetFunctionList, using the returned function list to invoke the C_Initialize
etc. functions. But what the actual function pointer point to is NULL. During
the initialization, the funciton pointer values were all assigned.
Hope for some advices eagerly.
You can reply me to the : [EMAIL PROTECTED]
Thanks in advance!
~
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cayley-Purser algorithm?
Date: Fri, 15 Jan 1999 09:08:04 GMT
William Whyte wrote:
[...]
> It is a public key algorithm, and it's based on work that
> Sarah did with us in Baltimore Technologies in Dublin when
[...]
> The idea we were working on was to use 2x2 matrices with entries
> modulo n, n the product of 2 primes (ie an RSA number). The
> security is therefore exactly the same as the security of an RSA key with
> the same modulus.
Hmmm, the stuff after "therefore" is certainly not implied by
the stuff before. I heard she proved it is of equivalent strength.
Is there actually a reduction from breaking the new algorithm to
breaking RSA?
> However, the encryption and decryption processes
> require only a small number of matrix multiplications rather than
> modular exponentiation, so both public-key operations (16 multiplications
> over the finite field) and private-key operations are as fast as a
> normal RSA private-key operation (17 multiplications).
Is that a typo? RSA _public_ key operations can be fast - like
17 modular multiplications (or two for that matter). The
private key operations are slow.
If she's shown how to do both public and private key operations
about as fast as (small public exponent) RSA public key operations,
and remain as strong as RSA, then that's really something.
As I understand it, the names of algorithms are determined
more by usage than by the inventor's christening. Much as I
respect her modesty, I thing we should call it the Flannery
cryptosystem.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Some Non-Random DES Characteristics
Date: 14 Jan 1999 21:53:28 -0800
In article <77ietq$rh0$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
>Further, due to its mathematical generality, I suppose that the
>"hash-function" argument advanced in item (d) and applied also in item
>(g) would be valid to a broad range of plaintext statistics, not just
>English and not just natural languages.
>Further application of these results are reported in [Ger99], using
As far as I can tell, the result presented in this document is that if you
mount a brute-force attack, you can break DES - noting that you only have
to brute-force the 56-bit key space, not the 64-bit space of possible
blocks. That's hardly news. Or am I misunderstanding the document?
--
The third girl had an upside-down penguin on Matthew Skala
her stomach, so the doctor told her, "I'll Ansuz BBS
examine you for free, if you and your (250) 472-3169
boyfriend will debug my Web server." http://www.islandnet.com/~mskala/
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Fri, 15 Jan 1999 02:18:25 +0100
"R. Knauer" wrote:
>
> >Thermal noise in a resistance is "fundamentally random."
>
> Yes, but is it crypto-grade random, since there a 1/f white noise
> spectrum associated with it?
>
The raw data probably isn't.
After you hash it, it should be.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: What is left to invent?
Date: Fri, 15 Jan 1999 11:49:17 GMT
Reply-To: [EMAIL PROTECTED]
On 14 Jan 1999 21:42:55 GMT, [EMAIL PROTECTED] (Jayant Shukla)
wrote:
>I just got hold of the paper by Bellare on Random Oracles. Hopefully
>it will clear things up.
If it is the one at:
http://www-cse.ucsd.edu/~mihir/papers/ro.html
then it sure would be nice if they would let you download the PDF
version.
Do you have another site in mind?
Bob Knauer
"Liberty lies in the hearts of men and women. When it dies there,
no constitution, no law, no court can save it."
--Justice Learned Hand
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Fri, 15 Jan 1999 12:02:03 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 15 Jan 1999 08:14:43 GMT, [EMAIL PROTECTED] (KloroX)
wrote:
>Earlier on, I proposed in this thread a simple fix for correcting a
>bias in the measurement of intervals between radioactive decays due to
>the finite half-life of the radioactive source. Taking t1 as the
>interval between event 1 and 2, and t2 as the interval between events
>2 and 3 (or 3 and 4), there is a statistical bias toward t1 < t2. The
>original RNG algorithm was (neglecting t1 = t2 for simplicity):
>
>If t1 < t2 output 0, else output 1
>
>I proposed to correct this bias by reversing the rule at every
>measurement (so that the condition alternates between t1 < t2 and t1 >
>t2). This eliminates the statistical bias. However, I overlooked the
>fact that it introduces a problem at least as bad: a correlation
>between even and odd bits. Odd bits are biased toward 0, even bits
>toward 1.
Check out the Hotbits site and see how the designer there does it.
http://www.fourmilab.ch/hotbits/how.html
>Since it seems that we have to resort to hashing or other mathematical
>"massaging" of the data
Which has every prospect of making the data non-random.
>to obtain a sequence that passes mathematical
>tests for randomness,
What mathematical test are you thinking about?
Remember that a crypto-grade random number cannot be characterized by
testing the number itself, only by characterizing the generator.
>no matter what the physical source of data is,
>doesn't this suggest that true randomness is absent in the physical
>universe?
True randomness is all over the Universe - that is the stuff upon
which Quantum Mechanics is based. It's algorithms that cause
non-randomness.
Bob Knauer
"Liberty lies in the hearts of men and women. When it dies there,
no constitution, no law, no court can save it."
--Justice Learned Hand
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: New Twofish Source Code Available
Date: Fri, 15 Jan 1999 12:05:48 GMT
On Thu, 14 Jan 1999 17:14:16 -0500, Uri Blumenthal
<[EMAIL PROTECTED]> wrote:
>Bruce, I know that you've had Java for a long time. You also
>had C code from the very beginning (I know - I ftp'ed it :-).
>But recently you posted that you got NEW IMPROVED source
>code for C and Asm - so my question is: are there
>any IMPROVEMENTS to Java code yet, similar to
>the C code improvements maybe?
No. It makes no sense to. These are all performance improvements,
and there's really no such thing as good performance in Java (for
pretty much of anything). Any application that needs good encryption
performance won't do it in Java.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Fri, 15 Jan 1999 12:08:38 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 15 Jan 1999 02:18:25 +0100, fungus
<[EMAIL PROTECTED]> wrote:
>> >Thermal noise in a resistance is "fundamentally random."
>> Yes, but is it crypto-grade random, since there a 1/f white noise
>> spectrum associated with it?
>The raw data probably isn't.
>After you hash it, it should be.
That is one of the recurring questions here - at least for me. What
hash are you proposing to make the data random? And can you offer
proof that it will actually make the data random?
I suspect that any algorithm will just introduce correlations, which
will make the data predictable and therefore non-random. I offer as
consideration for that the fact that in any algorithm, even a hash,
each bit is correlated to the next one in sequence by a calculation.
That is, two consecutive bits are correlated like f(n)*f(n+1), and
that is something that can be discovered by a cryptanalyst.
See: http://www.io.com/~ritter/RES/COMBCORR.HTM
Two recommendations for secure hashes have surfaced without any
supporting proof: CRC (16?) and LZ77. Maybe you have another.
Bob Knauer
"Liberty lies in the hearts of men and women. When it dies there,
no constitution, no law, no court can save it."
--Justice Learned Hand
------------------------------
From: Bernhard Treutwein <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math
Subject: Re: Random numbers in C: Some suggestions.
Date: Fri, 15 Jan 1999 13:38:40 +0100
Thanks to George Marsaglia for his post.
I recently stumbled over the following:
ISAAC: a fast cryptographic random number generator
(see http://ourworld.compuserve.com/homepages/bob_jenkins/isaacafa.htm)
can someone comment on it, is it worth a deeper look ?
--
Bernhard Treutwein Tel. +49-89-5996-642, Fax -615
Institut f. Med. Psychologie Ludwig-Maximilians-Universitaet
[EMAIL PROTECTED] http://www.lrz.de/~bernhard
-------------------------------- ---------------------------
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Fri, 15 Jan 1999 12:56:48 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 14 Jan 1999 22:32:11 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote:
>I often use 31-bit CRC's in crypto.
Is there a lookup table published for the 31-bit CRC, preferably on
the Web?
>So CRC mixing is really only appropriate for sources which have some
>amount of "true" randomness which must be accumulated. CRC cannot
>provide "a fine mixing" for LFSR's.
So you are not recommending a CRC for removing correlations from text
streams (even pre-processed ones) or digit expansions of pi. What
about Juola's suggestion of LZ77?
>It may be that in order to know if one has removed a correlation, one
>must first know what the correlation is. I am not sure that *any*
>technique would remove *all* correlations under *all* circumstances.
I suspect you are right. I can imagine some sort of indeterminancy in
all of this - like the only true random number is one that is
non-computable in the Turing sense.
It may be that once you can start computing with a number, it is not
random. But that analysis falls back on the generator, since Turing
non-computable numbers are such because they cannot be generated by an
algorithmic procedure.
Propositions:
1) If you can generate a number algorithmically, then it is
non-random.
2) If you operate algorithmically on a random number generated by a
TRNG, it is no longer random.
Here the term "random" means totally unpredictable, undecideable,
indeterminant - a number generated in such a way that all possible
numbers of a given length are equiprobable.
>But if we mix a lot of almost-random material into a small result, it
>seems like we have a good chance of getting pretty random stuff out.
Is there anything to back that up besides intuition?
>If you want a specific recommendation for re-mixing Pi, I would try
>mixing 4 different probes into the sequence. Selecting the probe
>positions (and even the probing, which might not be sequential or
>increasing) is part of the key. Other parts of the key could set
>shuffle some Latin squares for mixing; we could always use the same
>squares, or vary them according to the sequence itself, or another
>probe. We mix one pair, the other pair, then those results, and get a
>random value out.
There are two kinds of crypto-grade randomness: theoretical and
practical. What is needed is some kind of metric to characterize the
level of precision for generating a crypto-grade random number.
I believe that such analytical metric cannot be found. Only by an
actual experimental attack can you hope to gain an insight as to how
practically secure your system is.
>Probing Pi seems like a lot of work.
Presumably the BBP digit expansion for pi is not a lot of work. But
anyway, this is a theoretical discussion designed to expose useful
concepts. How they get implemented can be decided once we get the
concepts right.
>There is a remarkable lack of provable strength in cryptography.
Indeed. There may be a fundamental reason for that.
>At least with a Latin square we can say we get a balanced (unbiased)
>result from each mixing port, for any value on the other port, in a
>guaranteed absolute sense which does not depend upon infinite
>sequences.
How do you produce the actual square? If you start out with a square
where every row is the same and the digits are in ascending order - a
sort of "starting square" - how do you do the shuffle that square such
that every row is a different permutation? What algorithm do you use
for the shuffle?
BTW, what makes the Latin square method significantly different from a
CRC lookup table method?
>Even the comparison of two pulse periods is "algorithmic."
Yes, it is - and very primitive at that. But does it introduce any
correlation?
>http://www.io.com/~ritter/GLOSSARY.HTM#LatinSquareCombiner
>http://www.io.com/~ritter/ARTS/PRACTLAT.HTM
>http://www.io.com/~ritter/GLOSSARY.HTM#MixingCipher
>http://www.io.com/~ritter/#MixTech
You need a search engine on your site. :-)
Bob Knauer
"Liberty lies in the hearts of men and women. When it dies there,
no constitution, no law, no court can save it."
--Justice Learned Hand
------------------------------
** 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
******************************
