[30] in Best-of-Security
BoS: Reaaly cool unpatented public key algorithm!
daemon@ATHENA.MIT.EDU (David Mazieres)
Fri Feb 14 05:04:53 1997
Date: Fri, 14 Feb 1997 02:30:34 -0500 (EST)
From: David Mazieres <dm@reeducation-labor.lcs.mit.edu>
Reply-To: best-of-security@suburbia.net
Errors-To: best-of-security-request@suburbia.net
To: best-of-security@suburbia.net
Resent-From: best-of-security@suburbia.net
A while ago I sent a message here asking about unpatented (in the US)
public key agorithms--in particular ones with really fast signature
verification. Well, I appear to have found something that exceeds my
most optimistic wishes, and would like to know if anyone sees any
problems with this as it seems too good to be true (particularly since
no one else uses this algorithm).
The algorithm is based on the Rabin signature scheme, in which a
secret key is two primes (p, q), and the public key is the product of
the primes, N = pq. Rabin's scheme is based on the fact that taking
square roots mod N is provably as hard as factoring n (which is in
theory makes it stronger than RSA, though since the proof shows how to
factor n given some square roots it means you need to watch out for
chosen message (signing) or cyphertext (decryption) attacks. No
problem, just throw in a hash and/or some random padding and blow the
provable security, but not in a very worrisome way).
The annoying thing about Rabin's scheme is that every quadratic
residue m in N has 4 square roots (assuming GCD(m,n)=1). If you use
the Chinese remainder theorem to write a number m in ZN* as (mp, mq)
where mp = m mod p and mq = m mod q, then the Chinese remainders of
the square roots are of the form (x, y), (-x, -y), (x, -y), and (-x,
y). However, Hugh Williams found a really nifty solution to the
problem in:
A Modification of the RSA Public-Key Encryption Procedure.
H. C. Williams, IEEE Transactions on Information Theory,
Vol. IT-26, No. 6, November, 1980.
Note that this is NOT the technique that is usually cited for
Williams. For example, in Applied Cryptography, Schneier cites the
above paper, but then describes a more cumbersome way of working
around the 4 square root problem. Using the above technique [and
choosing a parameter Williams calls "e" to be 1, both for simplicity
and to avoid any resemblance to RSA--I suppose that could weaken the
cipher but I don't see how it breaks the proof of the cipher's
difficulty], I have implemented a cipher that has the following
properties:
* Public keys are just a multi-precision integer, easy to ship
around
* Signature verification takes under 200 microseconds on a Pentium
Pro 200 MHz with 1024 bit keys.
* Signing/decryption takes well under 100 milliseconds on a Pentium
Pro with 1024 bit keys.
* Cipher as hard to break as factoring, if I haven't botched
something horribly by misinterpreting the paper or using e=1.
So how does this cipher work? To generate a key, choose two prime
numbers p, q, such that:
p = 3 mod 8
q = 7 mod 8
Note: This means pq = 5 mod 8, so J(2, pq) = -1. [J is Jacobi]
This follows from the well-known formula for computing Jacobi's.
Then define N and k as:
N = pq
k = 1/2 * (1/4 * (p-1) * (q-1) + 1)
The public key is (N).
The private key is (N, k).
Define the following four operations. (Note D2 can only be
performed with the secret key.)
{ 4(2M+1) if J(2M+1, N) = 1
E1(M) = { 2(2M+1) if J(2M+1, N) = -1
{ key cracked! if J(2M+1, N) = 0 (completely improbable)
E2(M) = M^2 % N
D2(M) = M^k % N
{ (M/4-1)/2 when M = 0 mod 4
D1(M) = { ((N-M)/4-1)/2 when M = 1 mod 4
{ (M/2-1)/2 when M = 2 mod 4
{ ((N-M)/2-1)/2 when M = 3 mod 4
Public key operations on messages M < (N-4)/8 are as follows:
Encrypt: E2(E1(M))
Decrypt: D1(D2(M))
Sign: D2(E1(M))
Verify: D1(E2(M))
How does this work? Well, each number has 4 square roots, with
Chinese remainders (x, y), (-x, -y), (x, -y), and (-x, y). Since p =
q = 3 mod 4, we have that the Legendre values L(x, p) = - L(-x, p),
with the same for y and q. Thus, choose x and y without loss of
generality such that L(x,p) = L(y,q) = 1, and thus L(-x,p) = L(-y,p) =
-1. It follows from this that the Jacobi of the first two roots (with
respect to N), which is the product of the Legendres, will be 1, while
the Jacobi of the last two roots will be -1. Note further that the
first two roots will be additive inverses of each other, as will the
last two.
Now consider the four square roots of (E1(M))^2 mod N. E1(M) is one
of these, -E1(M) is another, and there are two more. However, since p
and q were chosen to make J(2,N) = -1, we know that J(E1(M),N) = 1.
That means E1(M) is either (x, y) or (-x, -y). But we also know that
E1(M) is even, and only one of (x, y) and (-x, -y) is be even. This
means that M is completely determined by (E1(M))^2 mod N.
More specifically, The well known Legendre formula tells us L(x, p) =
x^((p-1)/2) mod p. The definition of Jacobi gives us J(c, N) = L(c,
p) * L(c, q). Thus, J(c, N) = 1 implies L(c,p) = L(c,q) = +/- 1,
which implies c^((p-1)(q-1)/4) mod p = +/- 1 and c^((p-1)(q-1)/4) mod
q is the same (i.e. 1 if mod p was 1, q-1 if mod p was p-1).
Consequently, J(c, N) = 1 implies c^((p-1)(q-1)/4) = +/- 1, from which
it follows that D2(E2(c)) = E2(D2(c)) = c^((p-1)(q-1)/4 + 1) = +/- 1 *
c = +/- c. The result, since J(E1(M), N) = 1 is that D2(E2(E1(M))) =
+/- E1(M), but since E1(M) is even, and only one of E1(M) and -E1(M)
is even, M can easily be recovered by D1.
The best part of this is that signature verification is incredibly
cheap. Squaring is obviously way cheaper than arbitrary modular
exponentiation, and D1 is dirt cheap.
The only disadvantage I see here (other than the chosen message I
mentioned earlier) is that you loose a few bits off the top of your
message space because your message has to make it through E1 without
exceeding the modulus N.
Given my needs, this cipher seems superior to most of the other public
key systems in use today in simplicity (public keys are just numbers),
in speed, in avoiding patents, and maybe even in strength (though I
don't trust myself not to have done something stupid here and
misunderstood the paper, that's why I'm asking for advice here). What
makes me really suspicious is that no one else is using this. Does
anyone see any potential problems with this cipher?
Thanks a lot,
David
