From msuinfo!netnews.upenn.edu!newsserver.jvnc.net!yale.edu!yale!gumby!wupost!howland.reston.ans.net!pipex!lyra.csx.cam.ac.uk!pavo.csi.cam.ac.uk!cam-orl.co.uk!aph Tue Mar 15 21:44:05 1994
Newsgroups: sci.crypt,sci.crypt.research
Path: msuinfo!netnews.upenn.edu!newsserver.jvnc.net!yale.edu!yale!gumby!wupost!howland.reston.ans.net!pipex!lyra.csx.cam.ac.uk!pavo.csi.cam.ac.uk!cam-orl.co.uk!aph
From: aph@cam-orl.co.uk (Andrew Haley)
Subject: Fast stream cipher
Message-ID: <1994Mar15.223844.27749@infodev.cam.ac.uk>
Sender: news@infodev.cam.ac.uk (USENET news)
Nntp-Posting-Host: quince.cam-orl.co.uk
Organization: Olivetti Research Ltd, Cambridge, England.
X-Newsreader: TIN [version 1.2 PL2]
Date: Tue, 15 Mar 1994 22:38:44 GMT
Lines: 24

Schnorr described a fast stream cipher generator using RSA.  Starting
with a seed X 2N/3 bits long and an RSA modulus M which is N bits
long, calculate Y = X^3 mod M.  Use the most significant N/3 bits of Y
as the output of the generator, and recycle the remaining 2N/3 bits
into the generator.  Schnorr conjectures that this generator is as
secure as RSA.  This is an intriguing alternative to Feistel ciphers
like DES, if it can be made fast enough to be competitive.

Montgomery described a fast algorithm to calculate AB*(R^-1) mod M,
where R is some multiple of a computer's word size (so division by R
can be done by shifting); this algorithm has the great advantage of
not requiring long division.  If we were to use (X^3)*(R^-2) mod M as
our generator instead of Schnorr's X^3 mod M, we could generate N/3
pseudorandom bits with only two iterations of Montgomery's algorithm.
This is unlikely to be as fast as the fastest Feistel ciphers, but on
a computer with fast multiplication it will be quite close.  The only
problem is that I can not determine whether the extra multiplication
by R^-2 (mod M) weakens the generator in any way.  I don't see any
reason why it should, but I can't prove otherwise.  Can anyone help?

Andrew.

--
"Always keep an open mind, but not so open that your brain falls out."