Cryptography-Digest Digest #138, Volume #14 Sat, 14 Apr 01 02:13:01 EDT
Contents:
Re: please comment (Darren New)
Re: RSA CRT key? (Mark Wooding)
Re: Unnecessary operation in DES? (Mark Wooding)
Re: The 13th...:) (Mark Wooding)
Re: please comment ("Tom St Denis")
Re: _"Good" school in Cryptography ("was" I got accepted) (newbie)
Re: _"Good" school in Cryptography ("was" I got accepted) ("Peter L. Montgomery")
Re: Request comment on a new cipher design ("Scott Fluhrer")
Re: Ethernet & Encryption ("Bryan Olson")
Re: RSA CRT key? ("Bryan Olson")
Re: MD5 flaws ("Bryan Olson")
Re: please comment (Darren New)
�������� ("david")
Re: RSA modulus size and bits (Bryan Olson)
----------------------------------------------------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: please comment
Date: Sat, 14 Apr 2001 01:11:50 GMT
Tom St Denis wrote:
> Why not just use the honor system then?
Firstly, note that the OP didn't ask whether the process would work. The
question was whether it was patented.
Secondly, the calculation of how much it would cost may be driven by
business reasons that you don't want to be coding into your program. For
example, you want to issue a bill once a month only for the files that the
user actually sends off to get turned into chips. You don't want to charge
every time they save their work. And you don't want Joe reverse engineering
the program to find out how much you're charging Sam.
Whatever.
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
schedule.c:7: warning: assignment makes calendar_week
from programmer_week without a cast.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: RSA CRT key?
Date: 14 Apr 2001 01:23:44 GMT
massimo piccinetti <[EMAIL PROTECTED]> wrote:
> can you tell me where i can find the documentation of the algorithm
> ([Mil76]) to convert a RSAPrivateKey (modulus + private exponent only)
> to a RSAPrivateCRTKey (modulus, exponent, p, q etc..)
You need the modulus n and both the private exponent d and the public
one e. If you don't have the public exponent, you can try guessing that
it's one of the common ones (3, 17 or 65537 = 2^{16} + 1) until the
algorithm works.
The initial objective is to factor the modulus. The following algorithm
will do this.
Compute z = e d - 1. Since e d = 1 (mod \lambda(n)), we know that x^z =
1 (mod n) for all x. Also, since \lambda(n) is even (since p - 1 is
even, and \lambda(n) = \lcm(p - 1, q - 1)), we can write z = 2^s t,
where s > 0 and t is odd.
Invent some x at random, and compute x_0 = x^t. If x_0 = 1 (mod n) then
choose another x and try again. Now let x_{i+i} = x_i^2 for 0 <= i < s.
We know that x_s = 1 (mod n). Find x_j such that x_j != 1 but x_{j+1} =
1 (both mod n). If x_j = -1 (mod n) then we lose, so try again with a
different x. Otherwise, x_j is a nontrivial square root of 1 (mod n),
so \gcd(x_j - 1, n) is a nontrivial factor of n. Call it p and find q =
n/p.
(Why does this work? In order for y do be a square root of 1 (mod p q),
it must be a square root of 1 mod each of p and q -- the Chinese
Remainder Theorem makes this obvious. The only square roots of 1 mod p
are 1 and -1, and similarly for q. When we find a square root y of 1,
then, we have four cases:
1. y = 1 (mod p); y = 1 (mod q)
2. y = -1 (mod p); y = -1 (mod q)
3. y = 1 (mod p); y = -1 (mod q)
4. y = -1 (mod p); y = 1 (mod q)
Cases 1 and 2 are trivial and unhelpful. In these cases, we just have
to try again. Let's assume we're in case 3, then (case 4 is symmetric
anyway). We have y - 1 = 0 (mod p) and y - 1 = -2 (mod q). Assuming
that q > 2, then, y is a multiple of p (so it has a large common factor
with n) and is not a multiple of q. Hence \gcd(y - 1, n) is an
interesting factor of n.)
Now you're home and dry. All you need to do is compute d mod (p - 1), d
mod (q - 1) and q mod p.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Unnecessary operation in DES?
Date: 14 Apr 2001 01:37:20 GMT
Lassi Hippel�inen <[EMAIL PROTECTED]> wrote:
> John Savard wrote:
> <...>
> > Also, if DES is used to encipher ASCII characters, it changes how the
> > constant bits are located in the block.
One of the problems with DES is that it uses the low-order bit of each
key byte as the parity bit. This was clearly never intended to be used
with ASCII (or EBCDIC, for that matter). In fact, I think I'd class it
as a Mistake.
> I've heard this argument too, but referring to EBCDIC, not ASCII. In
> EBCDIC, digits and first alphabets have lots of leading zero bits. Since
> both Lucifer and EBCDIC came from IBM, the claim has some credibility.
No. In EBCDIC, digits are F0--F9. They have very few leading zero
bits!
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: The 13th...:)
Date: 14 Apr 2001 01:39:17 GMT
Jeff Moser <[EMAIL PROTECTED]> wrote:
> 20011304 and 20010413 are not prime :)
Why would anyone write the date as 2001-13-04 (yyyy-dd-mm)? That would
seem to suffer from all of the brain damage of the American date order,
without even the benefit of a widely-recognized standard to defend it.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: please comment
Date: Sat, 14 Apr 2001 01:47:04 GMT
"Darren New" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> > Why not just use the honor system then?
>
> Firstly, note that the OP didn't ask whether the process would work. The
> question was whether it was patented.
>
> Secondly, the calculation of how much it would cost may be driven by
> business reasons that you don't want to be coding into your program. For
> example, you want to issue a bill once a month only for the files that the
> user actually sends off to get turned into chips. You don't want to charge
> every time they save their work. And you don't want Joe reverse
engineering
> the program to find out how much you're charging Sam.
>
> Whatever.
My post was to suggest that it's insecure and not worthy of consideration.
Sure, if you want to purchase a license for a stupid product after people
warn you otherwise.... go ahead.
Tom
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: _"Good" school in Cryptography ("was" I got accepted)
Date: Fri, 13 Apr 2001 14:22:31 -0300
You mean Weizmann Institute of Occupied Palestine, I suppose.
Nicholas Hopper wrote:
>
> On Thu, 12 Apr 2001, newbie wrote:
>
> > Your first postulate is : "the university is the only place when you can
> > learn cryptography "
>
> Please review the original post in this thread:
> "Dear all,
>
> "Good" school in Cryptography wanted.
> Any recommendations?
>
> Thanks,
> kctang"
>
> The poster asked for a "school" in cryptography. I'm not qualified to
> comment on the quality of military or government instruction in these
> areas, because I haven't attended such a program, and the curricula are
> not public knowledge. Thus I gave a list of universities. If you know of
> other "schools" in cryptography, you are free to recommend them.
>
> > Your second is " you have to be strong mathematician to learn
> > cryptography "
>
> This is absolutely true.
>
> > Your third postulate is " only USA and Europe are the best place to
> > learn cryptography"
>
> The institutions of North America especially are the ones with which I am
> the most familiar. While I'm certain that there are fine cryptographic
> researchers at institutions in other parts of the world, none of them came
> immediately to mind, which means nothing. (I can think of several Japanese
> researchers, but I believe they are all employed in industrial positions).
> Since this is a public forum, anyone who knows about programs in those
> parts of the world, or who knows of other North American or European
> programs that I didn't list, is free to post about them.
>
> But one other university that came to mind about two minutes after my
> first post was the Weizmann Institute in Israel, which counts among its
> faculty Adi Shamir, Oded Goldreich, Moni Naor, Shafi Goldwasser
> (sometimes?) and Uriel Feige.
>
> =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> Nicholas J. Hopper
> Ph.D. Student in Computer Science
> Carnegie Mellon University
------------------------------
From: "Peter L. Montgomery" <[EMAIL PROTECTED]>
Subject: Re: _"Good" school in Cryptography ("was" I got accepted)
Date: Sat, 14 Apr 2001 03:26:23 GMT
In article <9b7h28$82h1b$[EMAIL PROTECTED]>
"Claus N�veke" <[EMAIL PROTECTED]> asks:
>Are there "good" Cryptography-schools in Germany?
The University of Essen hosted the 2000 conference
on elliptic curve cryptography. The conference web page
http://www.exp-math.uni-essen.de/~galbra/ecc2000.html
has links to other web pages.
--
The 21st century is starting after 20 centuries complete,
but we say someone is age 21 after 21 years (plus fetus-hood) complete.
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Request comment on a new cipher design
Date: Fri, 13 Apr 2001 21:00:24 -0700
Oops, my differential doesn't work. The prime used is 2**64+5, not
2**32+5...
Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
news:9b5oj7$coj$[EMAIL PROTECTED]...
>
> Joris Dobbelsteen <[EMAIL PROTECTED]> wrote in message
> news:9b3jb4$t7s$[EMAIL PROTECTED]...
> > It uses <r> rounds, where r is an integer always > 0.
> > The key schedule is ommited, as it's not designed yet, and needs to
> prevent
> > the use of weak keys that are very well possible.
> >
> > The cipher uses x86 byte order (little-endian?)
> >
> > Well, now the description:
> >
> > =========== Initial steps:
> > Divide the 128-bit block into 4 32-bit blocks: A, B, C and D. Where A is
> the
> > least significant and D the most significant.
> >
> > =========== Round, r denotes round number and always > 0 (thus starts at
> 1).
> > n = 9(r-1) ; used for the key
> >
> Possible differential: what if:
> A' - A = 13
> B = B'
> C = C'
> D' - D = 1
>
> > A = A + K(n) mod 2^32
> > B = B + K(n+1) mod 2^32
> > C = C + K(n+2) mod 2^32
> > D = D + K(n+3) mod 2^32 ; mixing up, against linearity with
> > additions.
> Differential unchanged.
>
> >
> > E = A XOR C
> > F = B XOR D ; Remember IDEA???
> E' - E = 13
> F' - F = 1
> both with some reasonable probability (2**-5???)
>
> >
> > L = E + (F << 32) ; 2^64+13 smallest prime >
2^64.
> > L = ( L * ( K(n+4) + ( K(n+5) << 32 ) ) mod (2^64+13) ) mod 2^64
> L = L'
>
> > L = ( L + ( K(n+6) + (K(n+7) << 32) ) ) mod 2^64
> > E = L mod 2^64
> > F = L >> 32 ; somwhat different.
> E = E'
> F = F'
>
> >
> > A = A XOR F ; IDEA here too...
> > B = B XOR E
> > C = C XOR F
> > D = D XOR E
> A' - A = 13
> D' - D = 1
> again, with some reasonable probability, possibly 2**-5
>
> >
> > L = B + (C << 32)
> > L = L |<< ( 20 + ( k(n+8) mod 2^5 ) ) ; Rotate here...
> > B = L mod 2^64
> > C = L >> 32
> These do not affect the differential
>
> >
> >
> > ======= Do some more rounds =======
> >
> > =============== End transformation
> > n = 9r ; (r is number or rounds)
> > E = A mod 2^16
> > F = A >> 16
> > G = B mod 2^16
> > H = B >> 16
> > I = C mod 2^16
> > J = C >> 16
> > K = D mod 2^16
> > L = D >> 16
> >
> > E = ( ( E * Low(k(n)) ) mod 2^16+1 ) mod 2^16
> > F = ( ( F * High(k(n)) ) mod 2^16+1 ) mod 2^16
> > G = ( ( G * Low(k(n+1)) ) mod 2^16+1 ) mod 2^16
> > H = ( ( H * High(k(n+1)) ) mod 2^16+1 ) mod 2^16
> > I = ( ( I * Low(k(n+2)) ) mod 2^16+1 ) mod 2^16
> > J = ( ( J * High(k(n+2)) ) mod 2^16+1 ) mod 2^16
> > K = ( ( K * Low(k(n+3)) ) mod 2^16+1 ) mod 2^16
> > L = ( ( L * High(k(n+3)) ) mod 2^16+1 ) mod 2^16
> >
> > A = E + (F << 16)
> > B = G + (H << 16)
> > C = I + (J << 16)
> > D = K + (L << 16)
> This end transformation doesn't disguise if B=B', C=C' originally
>
--
poncho
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: Ethernet & Encryption
Date: Sat, 14 Apr 2001 05:05:24 GMT
Latyr Jean-Luc FAYE wrote:
>I would like to have your comments on the solution I proposed on DES and
>RSA, the weakness of the system and the improvements that can be made.
[...]
>The objective of this assignment is to gain a detailed understanding of the
>different sub system/elements that need to be incorporated into a system
>which would perform a link level encryption. A functional specification of a
>link level encryption system that will provide secure transmission over an
>Ethernet network will be built to fill this need.
The problem I see here is integrating the system with
ethernet, not choosing cryptosystems.
[...]
>To make the exchange of data secure, the following conditions should be met:
>- The system must provide authentication and confidentiality
What is the identity of the parties? Is it just the 48-bit
ethernet address?
>- Only the data field of the frame must be encrypted as all the other parts
>should be able to be read by all the other nodes, especially the destination
>node field.
What goes into the protocol ID field? Is all traffic
encrypted, or can you support frames with un-encrypted data
at the same time?
Do you need an IV or message authentication code?
[...]
>3) The architecture of the system
Where does the cipher/authentication function sit? Can you
use ordinary ethernet hardware? If you need to include a
message authentication code (or an IV), then the payload of
the packets is smaller than with ordinary ethernet. Will
that confuse callers?
[...]
> These are the first two conditions that we have talked about
>above. Because of its rapidity in computation and its good level of
>confidentiality and authentication, DES has been chosen to do the
>conventional data encryption.
DES provides no authentication. The data packet could hold
anything, so you can't distinguish garbage from plaintext.
Is passing garbage to the network layer an adequate form of
authentication?
[...]
>The sending node and the receiving node share the same secret key as it is
>needed and used to encrypt and decrypt the data. As the secret key cannot be
>constant and is changed at each data transmission, a public key encryption
>is needed to transmit the new secret key each time data is transmitted.
[...]
>When the data transmission is finished, the secret key is erased from both
>the nodes. If the nodes want to communicate again, a new secret key will be
>generated from the sending node and sent to the receiving node.
That doesn't make sense at this level. The only unit of
communicate is the frame. There's no start or finish of
larger messages at the link level.
Also, is the session-key carrying frame encrypted? How does
the receiver know when a frame carries is a session-key?
What if such a frame is lost?
>2. RSA for key exchange
>
>We have decided to use RSA for the key exchange as the computation needed
>for the calculation of the secret key is not too heavy for a node, and that
>a third party was thus not necessary and not wished for the reason explained
>above. The Diffie-Hellman algorithm was not used even if it was more secure
>than RSA because it does not provide the authentication check of the two
>nodes before the exchange of the key.
Not really. If we fix a modulus m and generator g, and each
node has a public key g^x mod m (for private x), then each
pair of nodes automatically shares a secret, namely g^(x1 * x2)
for nodes 1 and 2. This is called "static Diffie-Hellman".
>3.Certification authority: exchange of public key
[...]
>4) Special computation requirements
[...]
>5) Generation of random numbers
These are generic crypto-problems. The real issue is how
the things get distributed over the link, and how many
components you'd have to re-engineer.
You've stated that the nodes get the CA public key
out-of-band. Are there any other out-of-band messages? Can
you describe how each node gets whatever else it needs via
ethernet frames?
--Bryan
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: RSA CRT key?
Date: Sat, 14 Apr 2001 05:21:30 GMT
In article <[EMAIL PROTECTED]>, massimo piccinetti wrote:
>Hello,
>can you tell me where i can find
>the documentation of the algorithm ([Mil76])
>to convert a RSAPrivateKey (modulus + private exponent only)
>to a RSAPrivateCRTKey (modulus, exponent, p, q etc..)
You need the public exponent too, (which is also in the
RSAPrivateKey).
While raising a random base to e*d-1, see if you get a
non-trivial square root of 1 along the way. If so, take the
gcd(n, square_root1 + 1) and that's a factor. If not,
repeat.
Below is Python code (which I posted once before).
--Bryan
|
| # Python code for factoring RSA modulus n using e and d
|
| def gcd(x, y):
| """Return the GCD of x and y."""
| while x>0:
| x, y = y%x, x
| return y
|
| def split_using_e_and_d(n, e, d):
| """Given a composite n and e, d such that
| e*d mod lambda(n) == 1, return a non-trival factor of n.
| Loops out or asserts false on bad inputs.
| """
| s = e * d - 1
| # Remove factors of 2 from exponent s
| while s & 1 == 0:
| s = s >> 1
| # Try bases until we find a factor
| for base in xrange(1, 999, 2):
| # Realy we should set base randomly
| a = pow(long(base), s, n)
| if a == 1:
| # Darn, we got to 1 without finding a square root
| continue
| # Keep squaring until we hit 1.
| while a != 1 and a != n-1:
| b = a
| a = a * a % n
| if a == 1:
| # Got it
| return gcd(n, b + 1)
| # Darn, the square root we found was -1.
| assert(0), "Something is very wrong."
|
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: MD5 flaws
Date: Sat, 14 Apr 2001 05:31:52 GMT
In article <[EMAIL PROTECTED]>, miathan wrote:
>Hello all...
>
>I keep encountering mentions of those supposed security flaws in MD5 in
>variuous documents, but seem unable to find what exactly those are.
>Does anyone know a document describing them and how serious the problems
>are?
It's a little old, so there may be more recent results, but
see
Hans Dobbertin "The Status of MD5 After a Recent
Attack", Cryptobytes vol 2 number 2, Summer 1996.
You can get it at:
ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto2n2.pdf
--Bryan
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: please comment
Date: Sat, 14 Apr 2001 05:38:10 GMT
Tom St Denis wrote:
> My post was to suggest that it's insecure and not worthy of consideration.
Fair nuff!
--
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
schedule.c:7: warning: assignment makes calendar_week
from programmer_week without a cast.
------------------------------
From: "david" <[EMAIL PROTECTED]>
Subject: ��������
Date: Sat, 14 Apr 2001 15:11:20 +0800
http://tacocity.com.tw/david/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: RSA modulus size and bits
Date: Fri, 13 Apr 2001 22:38:25 -0700
Paul Schlyter wrote:
[On making the RSA block fit for the modulus]
> 1. Make sure that E0 never becomes >= n.
Always do this.
> This means n should be as
> large as reasonably possible, i.e. at least its highest bit should be
> set to one. If your cleartext is ASCII characters which will have
> their high bits set to zero, this will be enough to ensure that E0
> always is smaller than n. And if your cleartext is some data smaller
> than the keysize which is to be padded with random bytes (a common
> situation when dealing with digital signatures), then pad the highest
> bytes and set the highest bit to zero to ensure that E0 always is
> smaller than n.
Always use one of the respected padding methods. See PKCS#1 for
the most popular example.
> 2. Don't bother trying to make n always larger than E0. Instead
> check E1, the result of the decryption: if E1 is correct, you've
> succeeded. If not, try to add n to E1 repeatedly [...]
I don't know of any system that does that, and it seems like a
foolish thing to do.
--Bryan
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
