Cryptography-Digest Digest #785
Cryptography-Digest Digest #785, Volume #12 Wed, 27 Sep 00 16:13:00 EDT
Contents:
Re: RSA and Chinese Reminder Theorem (Oliver Moeller)
Re: differnetials... (Tom St Denis)
Re: DES and Differential Power Analysis (Tom St Denis)
Re: Question on biases in random-numbers decompression (Bruno Wolff III)
Re: "Secrets and Lies" at 50% off (SCOTT19U.ZIP_GUY)
Re: PRNG improvment?? ([EMAIL PROTECTED])
Re: RSA and Chinese Reminder Theorem (Tom St Denis)
Re: Partial key PKE? (Mike Rosing)
Re: Cipher Illiteracy (Anton Stiglic)
Re: PRNG improvment?? ("Paul Pires")
Re: Other public key systems ("Joseph Ashwood")
Re: On block encrpytion processing with intermediate permutations (Bryan Olson)
Notice: Problems with DiehardC. ("Paul Pires")
Quantum Computing Conference(?) ([EMAIL PROTECTED])
Re: Chaos theory ("Douglas A. Gwyn")
Re: A New (?) Use for Chi ("Douglas A. Gwyn")
Re: IBM analysis secret. ("Douglas A. Gwyn")
Subject: Re: RSA and Chinese Reminder Theorem
From: Oliver Moeller [EMAIL PROTECTED]
Date: 27 Sep 2000 18:13:11 +0200
Soeren Gammelmark [EMAIL PROTECTED] writes:
I know that you can use the CRT to solve a system of equations: x mod
p(i) =3D a(i) where p(i) is prime. I've been trying to realise how this
can be combined with the RSA-decryption equation. So far I havent been
able to see how to form these two equations from the RSA decryption
equation. If anyone could show me, in detail if possible, I would
appreciate it. (I have read the section of number theory in Applied
Cryptography by Bruce Schneider - if it helps the explanation)
In the RSA algorithm, we have (assuming the key generation went right) two
primes: p and q. The modulus n equals p*q.
Moreover there is a public key d and a secret key e, such that
e*d = 1(mod phi(n))
Starting with a message m, picked from n, we have the cypher
c = m^d(mod n)
Decryption happens by computing
c^e = (m^d)^e = m^(d*e) = m^(1 + k*phi(n)) = m^1 * m^phi(n) = m * 1 (mod n)
BUT - you can safely assume c to be a large integer, say 300 decimal
digits. Computing c^e with standard modular exponentiation is still quite
slow (Schneider should have a description on this).
With CR *and* the additional knowledge of p and q we can go another (faster)
way:
(1) compute x := c MOD p
y := c MOD q
According to CR, x and y are uniquely encode c (mod p*q).
(2) compute xx := x^e MOD p
yy := y^e MOD q
with modular exponentiation.
(3) Now compute with CR the number c' (mod n), which is uniquely encoded
by xx and yy.
Due to a simple number theoretic argument (that I don't give here)
c' = c (mod n).
The important point is, that x,y,p, and q have about *half* the number of
digits compared to c and n. Modular exponentiation is very sensitive to the
number of digits, so the expensive step (the exponentiation) is
considerably faster and the extra time we spend on (1) and (2) is not
significant.
I heard of some hardware solutions, that go this way -- but it is dangerous,
for you have to 'hard-wire' the primes p and q. If an attacker is able to
extract these primes from the hardware (e.g. by some sophisticated
measurement of currents), he has broken the code.
(This is all the detail I have time for at the moment.)
Does this answer your question?
- oli http://www.brics.dk/~omoeller
*com-pu-ter*: device to enhance our capability to err. [EMAIL PROTECTED]
--
From: Tom St Denis [EMAIL PROTECTED]
Subject: Re: differnetials...
Date: Wed, 27 Sep 2000 16:08:43 GMT
In article [EMAIL PROTECTED],
Doug Kuhlman [EMAIL PROTECTED] wrote:
Tom St Denis wrote:
In article [EMAIL PROTECTED],
Doug Kuhlman [EMAIL PROTECTED] wrote:
SNIP
Also, Tom, in GF(2^8), -1/x^2 *is* a bijection, if you make a
little
proviso that 0 goes to 0 This follows from the fact that
squaring
is an isomorphism of a field of characteristic two (Frobenius).
but x^2 in GF(257) is not a bijection... so is it just in GF(2^8)?
In any finite field GF(p^n), raising to the pth power is a bijection.
So x^257 is a bijection in GF(257). Really, GF(2^8) and GF(257) are
VERY different finite fields.
I know that in GF(p) that the exponent and (p - 1) have to be
relatively prime for x^e mod p to have an inverse...
In fact, in any field of odd characteristic (think finite fields of
odd
size), squaring will never be 1-1. Cubing is 1-1 in fields like GF
(7),
GF(13), GF(16), but not GF(11), GF(8), or GF(17) [See the pattern?].
I know in any GF(2^2n) that squaring is a bijection, that in GF(2^2n+1)
cubing is, but I don't see the patten you are refering to...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
--
Cryptography-Digest Digest #785
Cryptography-Digest Digest #785, Volume #11 Mon, 15 May 00 23:13:01 EDT
Contents:
Re: Notes on the "Vortex" block cipher ("Trevor L. Jackson, III")
Re: Unbreakable encryption. (Eric Lee Green)
Re: What is a good Encryption program?? (Steve)
Re: Notes on the "Vortex" block cipher (John Myre)
Re: Notes on the "Vortex" block cipher (David A Molnar)
Re: Permutation Polynomials ("Dann Corbit")
An internet solution ... providing tiered security. ("C. Prichard")
X509 (Pablo Yaggi)
Re: Generator for ElGamal? (lcs Mixmaster Remailer)
Re: Unbreakable encryption. ("C. Prichard")
The IDEA simply restated. ("C. Prichard")
Tiered security solution for internet messaging ... ("C. Prichard")
Re: Permutation Polynomials (Polly Jim Steuert)
Date: Mon, 15 May 2000 17:09:32 -0400
From: "Trevor L. Jackson, III" [EMAIL PROTECTED]
Subject: Re: Notes on the "Vortex" block cipher
Tom St Denis wrote:
In article [EMAIL PROTECTED],
[EMAIL PROTECTED] (Terry Ritter) wrote:
On Mon, 15 May 2000 13:39:08 +0200, in
[EMAIL PROTECTED], in sci.crypt Runu Knips
[EMAIL PROTECTED] wrote:
Tom St Denis wrote:
There is some science behind cryptography whether you want to
believe
it or not.
And I think his dislike of Blowfish is only instinctive. I would
trust
Blowfish, too. It only requires a little bit too much resources for
some applications.
That particular answer of mine would have been the same for any other
cipher. The problem is not a particular cipher, the problem is in
trusting something which cannot be tested to see how closely it comes
to doing what we want it to do.
But that's true of *any* finite state machine.
Not quite. TR expressed the purpose of the cipher as if it were a positive
statement; "what we want it to do". But that expression is confusing because
what we want is a negative proposition. The purpose of a cipher is to not
leak information. Because the purpose is negative it is not testable. More
accurately, no finite sequence of tests can prove that no leaks are possible.
So therefore trust
nothing? I think that's a bit bitter. Realistic or not.
We need to send secure digital info, this is the best we can do. If
cipher X stops %99.99 of all messages from being read then Iwill
be happy with it.
But how will you know whether it stops any percentage of messages from being
read? You can _assume_ that the cipher prevents messages from being read, but
then you're dodging the question. The fundamental issue is what basis we have
for _making_ that assumption. In theory, none.
--
From: Eric Lee Green [EMAIL PROTECTED]
Subject: Re: Unbreakable encryption.
Date: Mon, 15 May 2000 21:16:30 GMT
[EMAIL PROTECTED] wrote:
A while back I posted some messages describing new encryption
algorithms that are not breakable. It used the Virtual Calc 2000
Sigh. Snake oil salesmen strike again.
The question is not whether any given algorithm is breakable. By definition,
if data can be encrypted, it can be decrypted. The question is how much effort
it will take to produce the proper decryption key. There are some good O(1)
attacks on producing encryption keys (e.g., bribe the key clerk to give you a
copy of the key!), aside from all the usual differential, known plaintext,
etc. attacks that can produce a key in less than 2^n operations (where n is
the bit size of the key) on poorly designed encryption algorithms.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer Visit our Web page:
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
--
From: [EMAIL PROTECTED] (Steve)
Subject: Re: What is a good Encryption program??
Date: Mon, 15 May 2000 22:58:34 GMT
On 15 May 2000 20:13:31 GMT, [EMAIL PROTECTED] (S. T. L.) wrote:
PGP can.
So can Scramdisk-- it makes "container files" that work like
small, extra hard drives when mounted. Everything that goes in
is encrypted on the way in, everything that comes out is
decrypted on the way out, but the container itself is never
decrypted. A very secure way to store local files, and an easy
program to use.
:o)
Steve
---Support privacy and freedom of speech with---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
PGP key 0xBFCE18A9 expires 5/15/01
RSA key available on request
--
From: John Myre [EMAIL PROTECTED]
Subject: Re: Notes on the "Vortex" block cipher
Date: Mon, 15 May 2000 17:55:51 -0600
"Trevor L. Jackson, III" wrote:
snip a bunch
The purpose of a cipher is to not
leak information. Because the purpose is ne
Cryptography-Digest Digest #785
Cryptography-Digest Digest #785, Volume #9 Sun, 27 Jun 99 02:13:04 EDT Contents: Re: A few questions on RSA (Gilad Maayan) Re: determining number of attempts required (S.T.L.) Re: Moores Law (a bit off topic) (david avery) Re: A few questions on RSA (S.T.L.) Re: DES-NULL attack (wtshaw) Re: A few questions on RSA (David A Molnar) Re: determining number of attempts required (JPeschel) From: [EMAIL PROTECTED] (Gilad Maayan) Subject: Re: A few questions on RSA Date: Sun, 27 Jun 1999 03:54:26 GMT Take the following encryption scenario: A 20 bit cyphertext is encrypted into a 20 bit cyphertext using a 1024 bit RTS pubic key. The public exponent is only about 100 bits long; the secret exponent would be around 900 (if I'm not mistaken). Anyhow, we're talking about a drastically small public key, and a correspondingly large secret key. I'm assuming, in the above scenario, that all of the following are true. Please note that I'm making a somewhat unconventional use of RTS - I know moduluses are usually kept in the public domain, etc. 1. An attacker knowing neither the modulus nor the public key, but knowing the exact length of the plaintext, would not be able to extrapolate the key from the cyphertext. 2. Let's assume the attacker knows the plaintext but not the modulus or the public key. The key space is indeed small in this case - only 2^20 - but this only means that each 20-bit combination would have an enormous amount of 'possible' 512/1024 keys (keys that, when used on the plaintext, would encrypt it as the known cyphertext). Therefore, you could test the entire keyspace (only about 1.05 million keys) to find a key that works, but you would have no way in hell of knowing which key was actually used. 3. Let's assume the attacker knows the plaintext, the cyphertext, the modulus, and the secret key (not the public key). For the reasons stated above, even though the effective key space is only 2^20, he would have to actually break 1024-bit RTS to know the key that was used in encryption - simply testing each one of the million-odd possible combinations would not yield the key. Furthermore, in our specific scenario, it would make no difference to an attacker that the public exponent was unusually small - 1024 RTS would be just as hard to break. I'd like to hear your comments on this. Also, I have another question, which appeared in the original message but wasn't answered to my satistfaction: Let's say you encrypt a message with triple DES, using two keys extrapolated from a key-seed by a function. You send the cyphered message together with the key-seed, without encrypting the key-seed in any way. If the functions are unknown to an attacker (forget the key-management issues), would it be able to extrapolate them from the key-seed and cyphertext? Many thanks, Gilad Maayan -- From: [EMAIL PROTECTED] (S.T.L.) Subject: Re: determining number of attempts required Date: 27 Jun 1999 04:42:01 GMT The password picked (by me, if you must know) was designed specifically to resist attacks :) I see several scenarios, increasingly interesting. I'd like to know which (if any!) are the case, actually. 1) You've encoded something important and have forgotten the exact key. However, certain details you stated about how fast you can try keys makes me think that the files are on some other computer, which you can't access. 2) You've given someone else guidelines to create a password (very, very unusual guidelines), and are now trying to crack it. Unlikely. 3) You picked a password to encode information, but have forgotten its exact contents AND are no longer allowed actual access to the encrypted data. This is the most interesting one. I'm getting really curious as to what you're trying to crack open! :-D -*---*--- S.T.L. === [EMAIL PROTECTED] === BLOCK RELEASED!2^3021377 - 1 is PRIME! Quotations: http://quote.cjb.net Main website: http://137.tsx.orgMOO! "Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8 E-mail block is gone. It will return if I'm bombed again. I don't care, it's an easy fix. Address is correct as is. The courtesy of giving correct E-mail addresses makes up for having to delete junk which gets through anyway. Join the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my .sig is shorter and contains 3379 bits of entropy up to the next line's end: -*---*--- Card-holding member of the Dark Legion of Cantorians, the Great SRian Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics Avid watcher of "World's Most Terrifying Causality Violations", "World's Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape" Patiently awaiting the launch of Gravity Probe B and the discovery of M39 Physics Commandment #2: Thou Shal
