Cryptography-Digest Digest #923, Volume #10 Tue, 18 Jan 00 13:13:01 EST
Contents:
Re: RSA (John Savard)
Re: Blowfish & pi. (John Savard)
Re: how to encipher ([EMAIL PROTECTED])
Is this stream cipher secure? (Salvatore Sanfilippo)
Re: MIRDEK: more fun with playing cards. (CLSV)
Re: ECC vs RSA - A.J.Menezes responds to Schneier (JCA)
Re: ECC (JCA)
Re: ECC vs RSA - A.J.Menezes responds to Schneier (JCA)
Re: ECC vs RSA - A.J.Menezes responds to Schneier (JCA)
Re: MIRDEK: more fun with playing cards. ("r.e.s.")
Re: ECC vs RSA - A.J.Menezes responds to Schneier (Bob Silverman)
blowfish key schedule ([EMAIL PROTECTED])
Re: MIRDEK: more fun with playing cards. (CLSV)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: RSA
Date: Tue, 18 Jan 2000 06:26:19 GMT
On Fri, 14 Jan 2000 14:44:23 +0100, "Kreuzer Michael"
<[EMAIL PROTECTED]> wrote:
>Hello,
>
>i have a big big problem. i must decode a rsa code. its my homework *g* can
>anyone help me?
>
>the code :
>
>key : 51,3
>
>616
That key must be wrong. If the key is a modulus and an exponent, then
all the cipher blocks should be <= the modulus. But 616 is bigger than
51.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Blowfish & pi.
Date: Tue, 18 Jan 2000 06:27:15 GMT
On Sat, 15 Jan 2000 06:30:38 GMT, XTR <[EMAIL PROTECTED]> wrote:
> Problem when to initialize P-array and S-array, that is,
>by taking fractional part of pi.
>After taking correct values for P[0] and P[1], the fractional
>part of pi goes all 0.00000....
>I'm using Turbo C++3.0, and the 'double' gives 64 bits datatype.
>Any better tip to overcome this?
Well, obviously you have to use something that can hold more than 64
bits of pi in it if you want to get more than 64 bits out.
Multi-precision arithmetic is what is needed.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: how to encipher
Date: 18 Jan 2000 08:09:27 -0500
[EMAIL PROTECTED] wrote:
> Christopher <[EMAIL PROTECTED]> wrote:
>> Yes, I know 2^17 mod n = (((((2^2 mod n) ^ 2 mod n) ^ 2 mod n) ^ 2 mod
>> n) * 2 mod n, but M is a very large number that M^2 cannot calculate
>> in my computer using long int.
> Can it handle an addition of two numbers mod n?
Unfortunately, for the size of n given, probably not ... unless you ensure
that you take your residues mod n as being between -n/2 and n/2 instead of
from 0 to n.
> SQR=0:j=0
> LOOP:
> If b_j=1, SQR=SQR+u_j mod n
> j=j+1
> if not finished with all the bits in u, then GOTO LOOP:
> (to calculate u*v mod n, expand v in binary and use the above)
Christopher <[EMAIL PROTECTED]> wrote:
> I am a beginner. I use p=20507,q=55889, e=67.
> So if I only obtain n=pq=1146115723 and e=67. I have find the private
> key from the public key, private key is d=85525323.
> Pls tell me how to decipher a text use d,
> since M^d mod n, M and d is too large handle is my computer.
You *would* have an n where 2n overflows long integers in QBasic,
wouldn't you <grin>!
Ah, well, as per my last post, you can write a routine to calculate the
product ab mod n (a,b positive) by accumulating terms by writing b in
its binary expansion, but then you have to, at least, add two numbers
modulo n. Of course, this looks impossible since that may overflow.
However, one can reduce mod n at each step - AND remember that instead
of taking numbers from 0 to n (in reducing modulo n) take numbers from
-n/2 to n/2 (e.g. in MOD5 calculations one can use 0,1,2,3,4 or
-2,-1,0,1,2) (for mod4, one would use -1,0,1,2) Now, if one does THAT
(in writing the multiplying routine which is used to create the
successive squares and the accumulated product) one will only be adding
numbers in absolute value smaller than n/2, and so, as long as n itself
(not 2n) does not overflow, one can succeed.
So ... after writing something up (in QBasic) I realized that your n was
so large that 2n overflowed and so wrote the appended QBasic programme.
It is set up to calculate a^d mod n for a,d,n>0 as long as n itself (and
d, of course) does not overflow long integers.
As a test (these agree with UBasic's modpow function) for n=1146115723,
d=85525323 I used it to calculate M^d for:
M M^d
2 573820127
3 471584706
321031413 446452693
Note that the size of n that you have is about the largest this QBasic
programme will handle, since 2n does overflow its (signed) long
integers. The programme will work on a system as long as it handles
signed integers and n does not overflow.
QBasic programme follows: To use, save a copy of this message, and
delete (from the copy) all lines from the start through the CUT_HERE
line. The residue (just the programme) can be loaded into QBasic and
run.
Check out the programme. The main routine is the mult& (long integer)
routine. It is used to get successive squares and accumulate the
products that give M^d mod n. You will note that in accumulating the
sums to give a*b mod n (b forced to be positive since its bits are
examined) during the accumulation, the terms are reduced mod n, but
taken always from -n/2 to n/2 so that the sum of any two is never larger
than n (so that if n does not overflow, neither will the sums).
You can manage to calculate M^d mod n as long as n does not overflow
long integers, but it is a pain (you cannot simply multiply two terms
mod n, for that may be as large as n^2, nor even write a simple routine
for the multiplication which adds terms mod n, for that may be so large
as 2n and even that overflows long integers with the n you have given -
but it can be done, using that approach, with some care to ensure you
use residues mod n from -n/2 to n/2).
QBasic is available on Win95 installation disks (maybe Win98?) and at
the MicroSoft site (the OLDDOS file there, when expanded, contains some
old DOS programmes, including the QBasic interpreter).
Note that UBasic is freely available, can handle numbers of thousands of
digits, and there are versions which run on a lowly 8088 (as well as 32
bit versions). The price is right, and its modpow(a,d,n) function gives
a^d mod n.
-=-=-CUT_HERE-=-=-
DECLARE FUNCTION mult& (a&, b&, n&)
DECLARE FUNCTION modpow& (a&, d&, n&)
REM programme to calculate a^d mod n as long as n does not
REM overflow long integers
REM in QBasic (\=integer division:&=long integer)
REM by John McGowan - 18 January 2000
CLS
PRINT : PRINT "This calculates a^d mod n for long integers."
PRINT : PRINT
INPUT "a (number to be raised to power)"; a&
INPUT "d (exponent = power)"; d&
INPUT "n (modulus)"; n&
ans& = modpow&(a&, d&, n&)
REM note that the mult routine provides a result modulo n, but
REM between -n/2 and n/2. It may be negative.
IF ans& < 0& THEN ans& = ans& + n&
PRINT : PRINT
PRINT "a^d mod n="; ans&
FUNCTION modpow& (a&, d&, n&)
REM a^d mod n as long as n does not overflow long integers
REM Initialize a^d to 1 (pow will accumulate this).
REM Initialize successive squares (powsq=powers/squares)
REM to a=a^(2^0) (first successive square of a).
REM Use local variable for expo[nent]
pow& = 1: powsq& = a&: expo& = d&
REM loop through all bits of the exponent
DO WHILE expo& <> 0
REM if the current bit in the exponent is one, then multiply in the
REM current successive square of a
IF (expo& MOD 2&) <> 0 THEN pow& = mult&(pow&, powsq&, n&)
REM get the next successive square of a and reduce the exponent
REM (to test the next bit)
powsq& = mult&(powsq&, powsq&, n&): expo& = expo& \ 2&
LOOP
REM note that mult& always returns a result mod n
REM and between -n/2 and n/2
modpow& = pow&
END FUNCTION
FUNCTION mult& (a&, b&, n&)
REM Multiplies a*b mod n for long integers
REM as long as n does not overflow.
REM To ensure this, all numbers mod n are forced to be
REM between -n/2 and n/2 instead of from 0 to n.
REM except b (whose bits we examine)
REM Set up changing variables
REM temp to hold successive doubles of a (temp&)
REM factor to get the bits of b (factor&)
REM prod& will accumulate the result (initialize to zero)
REM As we examine the bits of the second factor, we force it to
REM be positive.
factor& = b& MOD n&: prod& = 0&: temp& = a& MOD n&
IF factor& < 0 THEN factor& = factor& + n&
REM loop for all the bits in the binary expansion of b
DO WHILE factor& <> 0
REM check the next bit of the second factor, b:
REM if it is 1, then add in the correct multiple of a
REM but make sure temp is small
IF temp& > n& \ 2 THEN temp& = temp& - n&
IF temp& < -n& \ 2 THEN temp& = temp& + n&
IF (factor& MOD 2&) <> 0 THEN prod& = (prod& + temp&) MOD n&
REM try to keep size of prod& small (mod n&)
IF prod& > n& \ 2 THEN prod& = prod& - n&
IF prod& < -n& \ 2 THEN prod& = prod& + n&
REM double the "successive double of a" again and
REM reduce to get the next bit of the second factor
temp& = (temp& + temp&) MOD n&: factor& = factor& \ 2
LOOP
REM note that result is mod n, and between -n/2 and n/2
mult& = prod&
END FUNCTION
------------------------------
From: Salvatore Sanfilippo <[EMAIL PROTECTED]>
Subject: Is this stream cipher secure?
Date: 18 Jan 2000 14:36:29 GMT
Hi all,
I'm writing an opensource ecrypted shell and I need to know if the stream
cipher that I implemented is secure (or how much is secure).
The following is the description of the system I implemented, sorry if
it isn't in a mathematical form or if it's silly and trivial to break.
My email address is antirez@<antispamblabla>invece.org
bye,
antirez
DESCRIPTION
PERS aims to be a 'personal' secure remote shell. It isn't a ssh replacement
because its goals are different. You may use PERS if you need a simmetric
encrypted shell that allows remote login only to authorized users.
PERS aims also to be cryptographically secure: if you trust SHA1, blowfish and
Linux's /dev/urandom you can trust PERS. Contrary to ssh, PERS doesn't add
any overhead, so required bandwidth is the same that for normal telnet but
as side effect PERS will not save you from hijacking and others TCP/IP well
known problems (attacker will be able "only" to insert pseudo-random
bytes in your connection).
Total source length (except sha1.c and blowfish.c) is less than 1500 C lines
so it's trivial to audit the code in order to be sure that there aren't
buffer overflow or other vulnerabilities.
HOW IT WORKS
The client open a connection to server's 20001 port. The server send
40 random bytes, first 20 bytes are the input 'salt', last 20 bytes
are the output 'salt'. Both client and server compute two 160 bit
seed, inputseed and outputseed, inputseed = SHA1(shared secret+input salt),
outputseed = SHA1(shared secret+output salt), and reset two counters,
an input counter and an output counter. Now the client and the server can
create two secure random stream[1]: first 160bit of the input stream =
SHA1(inputseed+input counter) and output stream = SHA1(outputseed+output
counter). Counters will be increased by one for every interation. Since
sizeof(int) == 4 the stream will be repeat after 85899345920 bytes (80 Gb),
So after 85899345920 bytes client and server MUST exchange two new 20
bytes seed (but this is still not implemented). The shell session
is xored in input with the input stream and in output with the output
stream.
The shared secret is generated using the 'makekey' utility. Makekey build
the key using a file (or a device, i.e. /dev/[u]random) or random keys
hits as random source. The key is stored in a file, ecrypted with a 128 bit
blowfish. As you can guess, you need some secure way in order to exchange
the key file from server to client or vice versa (for example PGP). In effect
even if the encrypted key is pubblic an attacker also needs the blowfish key
in order to break the session, but a word-list attack become feasible.
In general it's a lot more secure if both encrypted key and blowfish key (the
passphrase) aren't pubblic.
[1] See Applied Cryptography second ediction, Bruce Schneier,
John Wiley & Soons, ISBN 0-471-11709-9, pp 421-428.
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Tue, 18 Jan 2000 15:40:34 +0000
Paul Crowley wrote:
> http://www.hedonism.demon.co.uk/paul/crypto/mirdek/
>
> All this is not academic: quite a few human rights people have been
> very interested in the possibility of a practical, secure hand cipher,
> and it seems at the moment that if Mirdek isn't it then we don't have
> one.
I have only glanced at Mirdek, but it looks nice.
One comment I have is: what is wrong with a modified
version of ARCFOUR, say restricted to 52 values?
Key setup would be slow but can be done in a reasonable
amount of time. It could even be skipped at the expense
of generating and transmitting a 52 card key using
thorough shuffeling. Encryption/decryption on the other
hand would be relatively fast.
Regards,
CLSV
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: ECC vs RSA - A.J.Menezes responds to Schneier
Date: Tue, 18 Jan 2000 07:59:15 -0800
Safuat Hamdy wrote:
> Jose Castejon-Amenedo <[EMAIL PROTECTED]> writes:
>
> > And we don't even know for sure if IF is NP.
>
> Pardon? IF: Given n given x < n, has n a factor larger than x which is
> smaller than n (yes/no) *is* definitively in NP. I'm sure you mean it is
> unknown whether IF is NP-complete.
Indeed. My apologies for my sloppiness.
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: ECC
Date: Tue, 18 Jan 2000 08:08:32 -0800
HRook wrote:
> When constructing a ECC, why would one chose F sub 2^m over F sub P?
>
> From what I've seen, the operations in F sub P are much simpler. Or, am I
> just reading things wrong?
My understanding is that how difficult operations will be depend more
critically
on the representation chosen. In F sub 2^m a polynomial basis representation
makes one manipulate binary polynomials, and the associated addition and
multiplication rules are arguably more amenable to efficient implementation
than integer addition and multiplication modulo p, as must be done in F sub p.
In addition, the particular irreducible polynomial chosen under F sub 2^m
also
has an influence on implementation efficiency. Finally, another nice feature of
F sub 2^m is that the squaring operation is simpler than the multiplication.
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: ECC vs RSA - A.J.Menezes responds to Schneier
Date: Tue, 18 Jan 2000 08:10:40 -0800
Greg wrote:
> In article <85ve97$do2$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Alfred Menezes comments on B.Schneiers article comparing RSA vs ECC.
> >
> > Available at:
> > http://www.cacr.math.uwaterloo.ca/~ajmeneze/misc/cryptogram-
> article.html
> >
> > Comments?
>
> He goes on to say...
>
> The rough estimates of RSA key lengths for equivalent security
> are 3072 bits, 7680 bits, and 15630 bits. Imagine the performance
> degradation incurred with RSA implementations at these key sizes,
> even with e=3!!
>
> Exactly...
While this is true, I can't help wondering if it has any value beyond
the
purely academic one?
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: ECC vs RSA - A.J.Menezes responds to Schneier
Date: Tue, 18 Jan 2000 08:14:11 -0800
Greg wrote:
> I believe that if ECC were to replace RSA as the standard pub key
> cipher in massively available and commonly used software packages
> like SSL, perception over ECC's quality of strength and its commercial
> acceptance would change in one year's time.
Well, yes. But that is precisely the issue. There are no solid reasons
why
ECC should replace RSA, at least not as of today.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Tue, 18 Jan 2000 08:50:14 -0800
"CLSV" <[EMAIL PROTECTED]> wrote ...
: Paul Crowley wrote:
:
: > http://www.hedonism.demon.co.uk/paul/crypto/mirdek/
: >
: > All this is not academic: quite a few human rights people have been
: > very interested in the possibility of a practical, secure hand cipher,
: > and it seems at the moment that if Mirdek isn't it then we don't have
: > one.
:
: I have only glanced at Mirdek, but it looks nice.
: One comment I have is: what is wrong with a modified
: version of ARCFOUR, say restricted to 52 values?
:
: Key setup would be slow but can be done in a reasonable
: amount of time. It could even be skipped at the expense
: of generating and transmitting a 52 card key using
: thorough shuffeling. Encryption/decryption on the other
: hand would be relatively fast.
Thanks for repeating my questions. I posted those ideas 3 days ago
-- "Changing ARC4's State-Space Size") -- and have seen no reply.
In that posting I also explain how to translate ARC4 source code into
card-manipulations. (Is it too much to ask that replies to these
ideas be posted in that thread which originated them?)
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: ECC vs RSA - A.J.Menezes responds to Schneier
Date: Tue, 18 Jan 2000 17:09:32 GMT
In article <8612p8$kic$[EMAIL PROTECTED]>,
Greg <[EMAIL PROTECTED]> wrote:
> In article <85ve97$do2$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> > Alfred Menezes comments on B.Schneiers article comparing RSA vs ECC.
> >
> > Available at:
> > http://www.cacr.math.uwaterloo.ca/~ajmeneze/misc/cryptogram-
> article.html
> >
> > Comments?
>
> He goes on to say...
>
> The rough estimates of RSA key lengths for equivalent security
> are 3072 bits, 7680 bits, and 15630 bits. Imagine the performance
> degradation incurred with RSA implementations at these key sizes,
> even with e=3!!
>
> Exactly...
I am not sure who the "he" is, in the above "He goes on to say..."
I will assume it is Alfred. I respect him a GREAT deal. But he is not
an expert on integer factoring and in particular is not an expert on
the use of the Number Field Sieve.
Allow me to point out that the RSA vs. ECC key size "equivalents"
is comparing apples and oranges. Why? Because the comparison
considers ONLY CPU time, while ignoring that fact that for keys over
768 bits, NFS is **** SPACE *** constrained, not time constrained.
We have a benchmark of 8000 MIPS-YEARS for RSA-512. The sieving
required "about" 50 Mbytes per sieve machine and the matrix took
10 days on a Cray using 2.3 Gbytes. The sieving took a couple of
months on a few hundred fast machines.
A 1024 bit key would require 2500 times the SPACE and about 6000000
times the TIME as RSA 512. Each sieve machine would require about
50M x 2500 = 125 Gbytes of memory. You would need 6million of them,
each with 125Gbytes to sieve for a 1024-bit number. Note that you
can't even ADDRESS 125G on a 32-bit machine! The matrix would require
2.3G x 2500 ~ 6 Terabytes of memory on a single machine. Even with
a CRAY with that much memory solving the matrix would take 60 Million
days. And matrix solving is a COUPLED problem. You can only get
so much speedup in solving it in a distributed fashion on a network.
A 3072 bit key is about 10^22 times as hard in terms of time as
512 bits and requires about 10^11 times as much space. Now, a
64 bit processor can't even address the amount of required memory
needed to hold the matrix.
And each sieve machine would require "about" 10^18 bytes of memory
to do the sieving.
Once you reach a point where a computation is effectively infinite
(in terms of current computer technology even assuming Moore's law
continues to hold for 20 years), then increasing the key size does not
buy one more security.
Furthermore, the "analysis" of the perfomance degradation assumes
that the RSA key has only two primes. One can get a big performance
enhancement by using multiple primes. E.g. if one used 6 primes
for a 3072 bit key (finding a 512-bit factor with ECM is effectively
infinite; it does not help) then one gets a BIG performance boost in
doing the RSA computations.
Indeed, a 1024 bit key with 3 primes is still way out of reach with
ECM and it is much faster than 2 primes to encode/decode. This
eliminates a large chunk of the advantage that ECM has over RSA:
faster operation at TIME equivalent key lengths.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: blowfish key schedule
Date: Tue, 18 Jan 2000 17:20:13 GMT
Hello all,
I have been taking a look at the blowfish algorthim. It certainly is
simple and lends itself to analysis.
The only downside seems to be the large amount of setup time required
for the S-boxes and the round keys in the P array.
As I understand it the purpose of the schedule is to yield key
dependent round keys and sboxes. Essentially, the blowfish key
schedule is a one way hash based on the input key.
It seems to me that the setup time could be dramatically reduced by
using a faster one way hasing algorithm. Several of the AES key
schedules spring to mind. Rc6, rijndael, and serpent all have key
dependent recursive hash functions as key schedules.
So why not uses the rc6 key schedule to generate the P array and
S-boxes for blowfish? The new algorithm would be a hybrid, rcfish or
blowrc :-)
The new algorithm should be mighty fast becuase the main loop of
blowfish is quite simple, involving only XOR and ADD.
--Matthew
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Tue, 18 Jan 2000 17:48:18 +0000
"r.e.s." wrote:
> "CLSV" <[EMAIL PROTECTED]> wrote ...
[...]
> : One comment I have is: what is wrong with a modified
> : version of ARCFOUR, say restricted to 52 values?
> Thanks for repeating my questions. I posted those ideas 3 days ago
> -- "Changing ARC4's State-Space Size") -- and have seen no reply.
> In that posting I also explain how to translate ARC4 source code into
> card-manipulations. (Is it too much to ask that replies to these
> ideas be posted in that thread which originated them?)
I must have missed your posting. Maybe you can repost it in
this thread?
One of the things that might be worth investigating
is if it is possible to strengthen the cipher (I'll call it "ARC52")
by utilizing the cards that do not correspond to a character.
If you define an alphabet consisting of the characters
"A".."Z", "0".."9", ".", " " you have 38 characters. Yet there
are 52 cards available. I was thinking about adding useless
characters at random points in the text. The problem is that
it should be done at random positions else you would give
information about the state space away.
Regards,
CLSV
------------------------------
** 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
******************************
