Cryptography-Digest Digest #884, Volume #10 Tue, 11 Jan 00 12:13:01 EST
Contents:
Re: Modular Inverse with RSA (James Pate Williams, Jr.)
Re: another newbie (Bob Silverman)
Re: Modular Inverse with RSA (Bob Silverman)
Re: Intel 810 chipset Random Number Generator ("Trevor Jackson, III")
Double transposition/playfair (Burma120)
Re: Clearer (hopefully?) example of 1-1 problem. (SCOTT19U.ZIP_GUY)
Re: Modular Inverse with RSA ([EMAIL PROTECTED])
Re: RSA encrypt ([EMAIL PROTECTED])
Re: Intel 82802 Random Number Generator (Guy Macon)
Re: Double transposition/playfair (John Savard)
Re: Simple Encryption ... (Anton Stiglic)
Re: Simple Encryption ... (Anton Stiglic)
Re: Double transposition/playfair (Jim Gillogly)
Re: Wagner et Al. (Guy Macon)
Re: Simple Encryption ... (Paul Koning)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Modular Inverse with RSA
Date: Tue, 11 Jan 2000 14:20:53 GMT
On 11 Jan 2000 05:58:49 GMT, [EMAIL PROTECTED] (Paul Rubin) wrote:
>Ryan Phillips <[EMAIL PROTECTED]> wrote:
>>After reading Applied Crypto I'm still confused on creating a private key
>>with RSA. if d=e^(-1) mod ((p-1)(q-1)), how do you calculate d.
>>
>>so if p = 47, q = 71, (p-1)(q-1) = 3220,
>>choose e at random that abides by the prime rules, e = 79 (just for
>>this case). now solve:
>>d =79^(-1) mod 3220 , the answer is 1019
>>
>>How do you get the answer 1019, and if someone could include another
>>example that would be great.
>
>The point is that (1019 * 79) % 3220 = 1.
>
>Look in a math book under "Extended Euclidean Algorithm" for how
>to do the calculation. Knuth vol. 2, "Seminumerical Algorithms" or
>Koblitz, "A Course in Number Theory and Cryptography" might be good
>places to start.
Three other references for the extended Euclidean algorithm:
_Cryptography: Theory and Practice_ by Douglas R. Stinson Figure 4.1
page 119;
_Handbook of Applied Cryptography_ by Alfred J. Menezes et. al.
2.107 Algorithm page 67;
_Introduction to Algorithms_ by Thomas H. Cormen et al. pages 811 -
812.
The second reference is available on-line. Search on Alfred J.
Menezes.
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: another newbie
Date: Tue, 11 Jan 2000 14:41:11 GMT
In article <[EMAIL PROTECTED]>,
"Markus Eiber" <[EMAIL PROTECTED]> wrote:
> Hi there,
> I am looking for information about how to calculate the practical
secrecy of
> a cipher.
Hi,
I think first that you need to define what you mean by "practical
secrecy". How can we measure that which has no definition?
> Is there a measure like the unicity distance for theoretical secrecy?
How
> can it be calculated?
In general, I would say an answer to your question is:
The time and space complexity function (as a function of key size) for
the best known attack.
Very few lower bounds have been proven on the complexity of breaking
ciphers and those that have are (AFAIK) mostly trivial bounds on
easily breakable ciphers.
--
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: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Modular Inverse with RSA
Date: Tue, 11 Jan 2000 14:35:44 GMT
In article <85ef2v$[EMAIL PROTECTED]>,
"Ryan Phillips" <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> After reading Applied Crypto I'm still confused on creating a private
> key
> with RSA. if d=e^(-1) mod ((p-1)(q-1)), how do you calculate d.
See Knuth, Vol. 2, "The Extended Euclidean Algorithm"
--
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.
------------------------------
Date: Tue, 11 Jan 2000 10:28:54 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Intel 810 chipset Random Number Generator
Guy Macon wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Trevor Jackson, III)
>wrote:
>
> >Because the example for a multi-threaded app works when applied at the OS level.
>To the OS the applications look like threads. The fact th
>
> Your posts bare all exceeding 80 collumns today, and somewhere between
> you and me everything after the 160th character disapears. Could you
> repost? I am interested in what you have to say.
Oops. Sorry.
------------------------------
From: Burma120 <[EMAIL PROTECTED]>
Subject: Double transposition/playfair
Date: Tue, 11 Jan 2000 07:18:35 -0800
Which is a stronger cipher, double transposition or double Playfair? If
one were to want to apply two rounds each of transposition and
Playfair, what order would be best (ie. PPTT, TTPP, TPTP, PTPT, PTTP,
TPPT)?
* 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: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Clearer (hopefully?) example of 1-1 problem.
Date: Tue, 11 Jan 2000 16:49:45 GMT
In article <85e25q$7e3$[EMAIL PROTECTED]>, "Gary" <[EMAIL PROTECTED]>
wrote:
>Compressed data can be seperated into 2 streams.
>A) Data from the original uncompressed data.
>B) Codes.
>
>eg Run length encoding example
>
>3,1,2,3,-5,7
>B,A,A,A, B,A (A byte from uncompressed data, B Code)
>The 1st number 3 (>0),indicates output next 3 bytes 1,2,3.
>The following byte -5 (<0) indicates next byte 7 is duplicated 5 times.
>decompressing to
>1,2,3,7,7,7,7,7
>
>Now take the following compressed data
>3,7,7,7,-5,7
>decompresses to
>7,7,7,7,7,7,7,7
>compresses to
>-8,7
>
>Redundancy in the original data stream of the compressed data doesn't result
>in 1-1.
>The same occurs if duplicate strings are added to dictionaries etc in ohter
>schemes.
>
>
>
>What about if redundancy in compressed data was used as codes.
>For example in new RLE:
>2+N duplicate bytes of B, followed by a byte value V indicates a run of
>N*256+V of B.
>
>so 1,2,3,4,3,3,3,1,6,7,8
> uncompresses to
>1,2,3,4, followed by 257 (256+1) 3's,6,7,8
>this seems to compress back OK.
>Unfortunately you can't compress data that has runs with length equal to the
>byte value.
>
>
Try this with my simple RLE you may be surprised?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website NOT FOR WIMPS
http://members.xoom.com/ecil/index.htm
Scott rejected paper for the ACM
http://members.xoom.com/ecil/dspaper.htm
Scott famous Compression Page WIMPS allowed
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
"The road to tyranny, we must never forget, begins with the destruction of the
truth."
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Modular Inverse with RSA
Date: 11 Jan 2000 11:07:04 -0500
Ryan Phillips <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> After reading Applied Crypto I'm still confused on creating a private
> key
> with RSA. if d=e^(-1) mod ((p-1)(q-1)), how do you calculate d.
> so if p = 47, q = 71, (p-1)(q-1) = 3220,
(why the extra work? LEAST_COMMON_MUTLIPLE(p-1,q-1)=1610 suffices)
> choose e at random that abides by the prime rules, e = 79 (just for
> this case).
> now solve:
> d =79^(-1) mod 3220 , the answer is 1019
> How do you get the answer 1019?
The extended Euclidean algorithm. Basically, one expands 79/3220 (a/c) as
a continued fraction. If you look at the penultimate convergent (b/d) (the
next convergent being A/C, a/c in reduced form - canceling common
factors) one has: d*A-b*C=+/-1 (this is true for any two successive
convergents, and the ultimate convergent is A/C) and so:
d*A=+/-1 mod C. For a,c relatively prime, A=a, c=C and you have
da=+/-1 mod c or, if this is +1, then d=a^-1 mod c and if this is -1, then
d=-a (or c-a) is a^-1 mod c.
Example:
3220/79=40+1/(1+1/(3+1/(6+1/3))) (continued fraction expansion)
The penultimte (before the last) convergent is:
40+1/(1+1/(3+1/6))=1019/25 (penultimate convergent)
So 79*1019-3220*25=+/-1 has to be true.
In this case, it comes out being +1, so 79*1019=1 mod 3220
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA encrypt
Date: 11 Jan 2000 11:13:13 -0500
Frank the root <[EMAIL PROTECTED]> wrote:
> Hum... I'm a bit new to cryptography but I would like to know how RSA can encrypt
> and decrypt a message ( in equations: c = m^e mod n and m = c^e mod n ) if there
> is not enough atoms in the universe to complete the operation c^d?? It might
> sound you like stupid question to you but it would fill my curiosity a lot, tank
> you.
Suppose you want to calculate 5^3 mod 7
You could do
5*5=25
25*5=125
and then take the remainder mod 7, 125=6 mod 7
An easier way is:
5*5=25
Now reduce this (since we only want mod 7) to get:
5*5=4 mod 7
Then 5*4 (which is 5*25 mod 7) is 20 mod 7 = 6 mod 7
By reducing the result mod 7 after the first multiplication we never had
to see the large number 125 (only one multiplication, which can be as
large as 7^2, almost, and taking its remainer each time).
In calculating a^b mod c, one has various multiplications (using the
expansion of b in binary, successive squaring and multiplying various
terms that result so one does not have to do "b" multiplications which
would take *WAY* too long <grin>) and each one is reduce mod c before the
next. That keeps the numbers (in getting the result mod c) in check.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Intel 82802 Random Number Generator
Date: 11 Jan 2000 11:22:08 EST
(The correct name of the chip in question is the Intel 82802 Firmware Hub.
The Intel 810 chipset contains a 82802, but so do the 820 and the 840, and
Intel will doubtless use this chip in future chipsets.)
>Scott Nelson wrote:
>
>>Bradley Yearwood wrote:
>>
>>> ... which appears to indicate a worst-case rate of
>>>random byte production of around 222 bytes/sec.
>>>
>>Actually, the worst case is infinite,
>>but the _average_ is claimed to be 75Kbits per second.
>>The odds against having to wait 4.5ms are extreme,
>>thus the recommendation that if you have to wait longer
>>than that, you should give up and assume there's a problem.
Cryptography Research, Inc. has a paper showing the internals.
[ ftp://download.intel.com/design/security/rng/CRIwp.pdf ]
I was right about there being a state machine, but not about it
doing SHA1 (most of the docs don't make it clear that the SHA1
is to be done in software, but the it's there if you look hard).
The state machine contains (along with the cell programming logic)
a Von Neumann corrector with the following truth table:
zero followed by zero equals no output
zero followed by one equals one
one followed by zero equals zero
one followed by one equals no output.
Clearly a long string of all ones or all zeros is possible but not
probable, which makes long delays possible but not probable.
Some of the docs imply an 8 bit buffer, but this paper says that
the buffer is 32 bits fed by a 75Kbps (average) bit stream. It's an
interesting security question whether the OS or application should
have a FIFO buffer of this stream that might be read by an attacker.
The Von Neumann corrector outputs an average of one output bit
for every 6 input bits. I believe that a true random input
stream would have a 4:1 ratio, not 6:1. I am a crypto newbie but a
electronics engineering expert, and given the method described, a
corrolation between sucessive bits before the Von Neumann corrector
doesn't suprise me.
I was glad to see that Intel is *not* using the thermal noise of
a resistor as a source for the raw bits, but is rather using the
difference between two such resistors. Matching of resistor
characteristics on a single die tends to be very good, and external
electromagnetic fields are (imperfectly) rejected. The small
physical size of an onchip solution also helps by making the
effective loop area of the internal parts small, which makes
them poor antennas.
Could one of you fellows who know more about crypto take a look
at the way Intel suggests doing the SHA1 and comment on it?
It seems that you could write a device driver to get at the output
of the chip and then use whatever method you choose.
[ ftp://download.intel.com/design/security/rng/CRIwp.pdf ]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Double transposition/playfair
Date: Tue, 11 Jan 2000 09:34:04 GMT
Burma120 <[EMAIL PROTECTED]> wrote, in part:
>Which is a stronger cipher, double transposition or double Playfair? If
>one were to want to apply two rounds each of transposition and
>Playfair, what order would be best (ie. PPTT, TTPP, TPTP, PTPT, PTTP,
>TPPT)?
I'd go for PTPT.
PP produces a digraphic cipher, even if it is a more complicated one
than just P.
Transposing after Playfair makes it hard to determine which two
letters belong to the same digraph. Transposing before provides
enciphered digraphs produced from letters with normal frequency, so
there is still quite a bit to work on. Thus, PT is stronger than TP.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Simple Encryption ...
Date: Tue, 11 Jan 2000 11:41:01 -0500
David Wagner wrote:
> In article <85cncq$5b7$[EMAIL PROTECTED]>,
> Derek Potter <[EMAIL PROTECTED]> wrote:
> > There are times when it would be cool (Ok, so
> > you now know this is going to be one of *those*
> > questions!) to be able to encrypt something not
> > so much to stop it being read by third parties
> > but to prove to the *recipient* that you have
> > some information but you aren't prepared to
> > divulge it *yet*.
>
> The primitive you want is bit commitment. See Schneier for protocols.
What you realy want is a ZK proof (as I mentioned in my other posting),
which can be derived from a bit commitment scheme or some other
scheme (a verifiable secret sharing for exemple). A simple bit commitement
scheme doesn't do the trick, and could be to low level to build the ZK proof
you need...
Anton
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Simple Encryption ...
Date: Tue, 11 Jan 2000 11:44:14 -0500
Paul Koning wrote:
> Derek Potter wrote:
> >
> > There are times when it would be cool (Ok, so
> > you now know this is going to be one of *those*
> > questions!) to be able to encrypt something not
> > so much to stop it being read by third parties
> > but to prove to the *recipient* that you have
> > some information but you aren't prepared to
> > divulge it *yet*.
>
> That's easy.
>
> Put the description in a text file, and sign it
> with a "detached signature" (as PGP calls it).
> Publish the signature. Keep the original
> file secret.
>
> At some later time you can publish the text file,
> and anyone can then verify that the previously
> published signature is valid for that file.
>
> paul
That doesn't work if you want to imediatly proove
your knowledge, without letting people gain knowledge
of what it is...
It works if you don't care that everybody else figures
out the answer when they are to be convinced that you
know the answer.
Anton
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Double transposition/playfair
Date: Tue, 11 Jan 2000 16:53:34 +0000
Burma120 wrote:
> Which is a stronger cipher, double transposition or double Playfair? If
> one were to want to apply two rounds each of transposition and
> Playfair, what order would be best (ie. PPTT, TTPP, TPTP, PTPT, PTTP,
> TPPT)?
Bletchley Park reckoned that double transposition was stronger.
The Germans used double transposition for their secret police commo,
but in 1941 switched to double Playfair. After the switch Bletchley
was much more successful in reading their traffic, and for over a
year were able to track information that wasn't covered in other
broken systems.
Double Playfair is not as simple as it looks from Bauer and the other
authors I've seen published. I found a paper from Bletchley in the
declassified NARA "Open Door" documents: besides using two squares
like a Two-square cipher, it has two encryption steps. The encrypted
digraph is pushed through the same cipher process a second time.
See http://www.pbs.org/wgbh/nova/decoding/faceoff.html for links to
descriptions of double Playfair and double transposition as used for
actual traffic in WW2.
Regarding the order of two rounds each, it probably doesn't matter
much as long as you don't have PP together. If you had PPT you could
test the result of unwinding the transposition with repeated digraphs.
I would think TTP would be a very challenging hand cipher, but subject
to the human problems you read about in "Between Silk and Cyanide". A
hand cipher must be straightforward enough for someone with a day job
not involving cryptography to use.
--
Jim Gillogly
Highday, 20 Afteryule S.R. 2000, 16:37
12.19.6.15.10, 6 Oc 18 Kankin, Fourth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Wagner et Al.
Date: 11 Jan 2000 11:55:17 EST
In article <851144$o$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tom St Denis) wrote:
>You just don't get it, do ya?
>
>If you can't protect against trojans, why bother bloating the code to
>try and protect against them. Thicker condoms is not always safest....
>
>I clear the stack and encrypt the keyfile. That's about all I can do.
>That's all I do.
If you claim that you evaluated this issue and decided on your current
path, I would respect that. That's not what you are claiming.
What you are claiming is the following:
[1] The authors of PGP were foolish to provide better security than
you provide (based on the logical fallacy that imperfect solutions
are no better than no solution at all.)
[2] Despite the above argument, you are for some reason not foolish
to clear the stack and encrypt the keyfile (assertion without evidence
or reasoning behind assertion.)
[3] Several apparently intelligent people who disagree with you
"just don't get it" (logical fallacy of ad hominem attack.)
In my opinion, you have failed to prove your case, and therefor a
rational customer would go to your competitor who provides the
security features that you claim to be without merit.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Simple Encryption ...
Date: Tue, 11 Jan 2000 11:59:09 -0500
"r.e.s." wrote:
> SHA1 hashes "any" input document into 20 bytes of output
> (illustrated below as 5 blocks of 4 hex chars each, with
> each hex char represented by 2 ascii chars, and blocks
> separated by a space, for a total of 44 characters.)
>
> I don't know the practical limitations on just how large
> the input can be without encountering problems, but it's
> probably huge.
2^64 bits.
paul
------------------------------
** 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
******************************
