Cryptography-Digest Digest #927, Volume #10 Wed, 19 Jan 00 03:13:01 EST
Contents:
Forward secrecy for public key encryption (new proposal, long) (David Hopwood)
Re: Java's RSA implimentation ("Artemios G. Voyiatzis")
----------------------------------------------------------------------------
Date: Wed, 19 Jan 2000 07:27:03 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Forward secrecy for public key encryption (new proposal, long)
=====BEGIN PGP SIGNED MESSAGE=====
It seems the consensus here is that for the two methods described
in the Maurer-Yacobi paper [MY96], there isn't a large enough
security margin between the factoring problem and the discrete log
problem, at least using currently practical parameter sizes.
However, here's another possible way to embed a trap-door into the
DLP for Z*_m, which (if I haven't made any mistakes) could be much
more practical.
Instead of using index calculus or Pohlig-Hellman to calculate the
discrete logs during key pair generation, we select a base element
that generates a subgroup, and a method of obtaining public values
in that subgroup, such that logs of these values can be calculated
using Pollard rho and the CRT, if (and hopefully only if) the
factorisation of n is known. The idea is to try to ensure that the
attacker has to work in a large subgroup (or the whole group),
while only discrete logs in small subgroups are needed for key pair
generation. This also has the advantage that Pollard rho is much
easier to implement than index calculus methods.
Key pair generation [simplified version; see later for a necessary
modification]:
1. Choose distinct random primes p_1..p_r, of roughly equal size
and where the factorisations of p_i - 1 are known, such that
the values (p_i - 1)/2 are odd and pairwise relatively prime,
and q_i is a prime dividing (p_i - 1)/2 for each i.
Let m = product[p_i: i = 1..r]
q = product[q_i: i = 1..r]
z_i = (p_i - 1)/q_i
s = sum[z_i: i = 1..r]
The q_i (which are necessarily all distinct) should be primes of
a size such that Pollard rho is practical in a subgroup of size
q_i for each i, but not in a subgroup of size q.
The z_i must not be smooth, and should preferably each be twice
a prime number.
2. Select elements alpha_i that generate subgroups of sizes q_i, as
follows:
a) Choose an element g of Z*_m that is primitive in each of the
prime fields Z_{p_i}, i.e., such that for i = 1..r, p_i - 1
is the smallest exponent for which g^(p_i - 1) = 1 (mod p_i).
(To test whether g is primitive in Z_{p_i}, check that
g^((p_i - 1)/a) mod p_i != 1 for each prime factor a of
p_i - 1.)
b) Compute alpha_i = g^z_i for i = 1..r.
alpha = product[alpha_i: i = 1..r].
[Note that:
- g has maximal order phi(m) in Z*_m,
- alpha_i has order q_i,
- alpha has order lcm[q_i: i = 1..r] = product[q_i: i = 1..r] = q,
- alpha = g^sum[z_i: i = 1..r] = g^s.]
Let R be a hash of the public key - see later for the precise
definition. (R will be used as a random seed for the generation
of public values; a hash of the public key is a convenient way
of doing this that does not require extra data to be stored.)
3. For t = 1..T (where T is the number of time periods),
a) Let y_t = I(s, R, t).
(I is a public function, described later, that maps its input
to a "random" element of the subgroup generated by alpha. Its
result will be beta^s for some known element beta.)
b) Calculate the discrete log x_t = log_alpha(y_t).
Note that since y_t = beta^s, alpha = g^s, and alpha_i = g^z_i,
log_alpha(y_t) = log_g(beta) (mod q)
= log_alpha_i(beta^z_i) (mod q_i)
[beta^z_i is guaranteed to be in the subgroup of order q_i
generated by alpha_i.]
Therefore we can calculate x_t as follows:
i) For each i = 1..r, use Pollard rho (see Algorithm 3.60 of
[HAC], or [Pollard]) to compute the discrete log w_i of
beta^z_i mod p_i to the base alpha_i.
ii) Solve the system of congruences
x_t = w_1 (mod q_1 - 1)
: : :
x_t = w_r (mod q_r - 1)
by the Chinese remainder technique (e.g. Algorithm 14.71
of [HAC]). Note that x_t will be in the range [0, q-1].
4. Let l_q be the length of q in bits (i.e. floor(log_2(q))).
Retain (m, alpha, s, l) as the public key, (x_1..x_T) as the
private key, and delete all other values (p_i, q_i, q, z_i,
alpha_i, and any intermediate results).
Encryption [simplified version]:
1. Obtain the recipient's authentic public key (m, alpha, s, l_q),
and the current time period t (or a time period in the near
future, to take into account delays in delivering a message).
2. Calculate R = H(m, alpha, s, l_q)
(where H is a public hash function),
y_t = I(s, R, t).
3. Encrypt the message using a suitable Diffie-Hellman-based PK
encryption algorithm (I recommend [DHAES]), with y_t as the
public value and alpha as the base. The length of the exponent
for the ephemeral key should be at least l_q.
Append t to the ciphertext.
Decryption [simplified version]:
1. Extract t from the ciphertext, and decrypt using the chosen
DH-based algorithm, with x_t as the private value.
This leaves I() unspecified. Since most elements of Z*_m are not
in the subgroup generated by alpha, we cannot directly use, say, a
hash of R and t as the public value.
We could first obtain an element beta in the maximal order subgroup
generated by g, and then use y_t = beta^s. beta could be found using
the same method as in section 2 of [MY96], by squaring some arbitrary
element (the reason for the condition that the values (p_i - 1)/2 are
odd and pairwise relatively prime is to make this method applicable).
However, we also have to prevent the attack described in [MY96],
that allows factoring the modulus when a secret key is revealed.
As suggested in that paper, we blind the private key values by
multiplying by a secret value u. (This corresponds to t in the
paper, but we're already using the letter 't' for time periods.)
Like the other private information of the "trusted authority",
u is deleted after key pair generation.
The [MY96] method as it stands is inconvenient for a non-identity-
based scheme, because it requires both the sender and recipient to
be "users". To remove this requirement, we create a notional "dummy"
user whose private exponent (actually, a value derived from it) is
made public. If the private keys for different periods cannot be
inferred from each other, this should not weaken security. The
agreed key will be based on the dummy user's private exponent, the
recipient's private exponent, and an ephemeral (per-message)
exponent known only to the sender.
[Note that in everything that follows, "^" denotes exponentiation
modulo m, and "." denotes multiplication of exponents as integers.]
Let F be a suitable pseudo random function.
Let I(s, R, t) = F(R, t)^(2.s).
Suppose that the dummy user's public group element is
yD = F(R, 0)^(2.s) (note that the time period 0 is reserved), and
its private exponent is xD = u.log_alpha(yD). Alice wishes to
send a message to Bob, who has public key (n, alpha, s, l_q), in
time period t. Bob's public group element is yB = F(R, t)^(2.s),
and his private exponent is u.log_alpha(yB).
The DH shared value will be
alpha^(u.log_alpha(yD).log_alpha(yB).k)
where k is the ephemeral exponent.
Alice can compute this as (yB^xD)^k, while Bob can compute it as
(yD^k)^xB (assuming Alice has sent him yD^k).
We can simplify this by noting that
(yB^xD)^k = (F(R, t)^(2.s.xD))^k
Let h = 2.s.xD mod phi(m)
= 2.s.u.log_alpha(yD) mod phi(m)
Then
(yB^xD)^k = (F(R, t)^h)^k
Also rename yD to y. The public key now becomes (m, y, h, l_q)
(alpha and s are no longer used, so they can be removed).
We add a step to the key pair generation to choose u at random
from [1, phi(m)-1], and redefine x_t as
x_t = u.log_alpha(y_t) mod phi(m)
With this redefinition, the private key is still (x_1..x_T).
Encryption and decryption must be modified as follows (this time
writing out the definition of DHAES in full, adapted as necessary):
Let H be a public hash function.
Let F be a pseudo random function that maps a bit string to the
set of integers [2, n-2]. (This could for example be based on
MGF1 from [P1363].)
Let SYM be a symmetric encryption algorithm, with key length eLen.
Let MAC be a message authentication code, with key length mLen.
Notes:
- H, F, SYM and MAC must be agreed or standardised in advance.
- For simplicity, if F and/or MAC are based on a hash function,
H should be used.
- SYM will only be used to encrypt a single message under a
given key, so it can be either a stream cipher or a block
cipher.
- The issue of encodings for integers, inputs to H and F, and
ciphertext is glossed over below - these need to be unambiguous.
- See [DHAES] for clarification of the notation, and a rationale
for various features (e.g. why the ephemeral public value U is
included in the input to the hash used to generate cipher and
MAC keys).
Encryption [full version]:
1. Obtain the recipient's authentic public key (m, y, h, l_q), and
the current time period t (or a time period in the near future,
to take into account delays in delivering a message).
Let M be the plaintext message.
2. Choose a random k in [1, 2^(l_q+1) - 1].
[This differs from [DHAES], where k (which is called 'u'),
is chosen from [1, |G|]. In this case |G| would be the size
of the subgroup, q, which would then need to be included in
the public key. I'm not sure that would be a good idea (see
the "Open questions" section later). Of course this
invalidates the DHAES security proofs, but they would be
invalidated anyway by the other changes.
It would also be possible to use [1, 2^(l_q+b) - 1] for
some b > 1; as b increases, any bias in the selection of
U = y^k from the elements of the subgroup becomes
negligable.]
3. Calculate R = H(m, y, h, l_q),
X = (F(R, t)^h)^k,
U = y^k,
hash = H(U, X),
macKey = first mLen bits of hash,
encKey = next eLen bits of hash after macKey,
encM = SYM.enc(encKey, M),
tag = MAC.gen(macKey, encM),
The ciphertext is (t || U || tag || encM).
[Note: The pseudocode for encryption in figure 2 of [DHAES]
is incorrect; it applies the MAC to M, whereas the rest of
the paper, including the security proofs, applies it to encM
as shown here.]
Decryption [full version]:
Note that an output of BAD means that the ciphertext was not valid.
1. Parse the ciphertext as (t || U || tag || encM)
(if it cannot be parsed this way, or if t = 0, output BAD).
2. Calculate X = U^x_t,
hash = H(U, X),
macKey = first mLen bits of hash,
encKey = next eLen bits of hash after macKey.
If MAC.ver(macKey, encM, tag) fails, delete any intermediate
results, and output BAD.
Otherwise, the plaintext is SYM.dec(encKey, encM).
Efficiency:
Key pair generation requires O(sum[sqrt(q_i): i = 1..r]) work,
and can be made practical if the q_i are less than about 50 to
60 bits. q should be at least 160 to 200 bits to prevent square
root attacks, which implies that r (the number of factors of m)
will be about 3 to 8.
Encryption requires 3 exponentiations modulo m (if more than
one message is sent to a single recipient, the result of one of
these can be cached). These can all be precomputed before the
message is known, but not before the recipient is known. Two
of the exponentiations are with a "short" exponent, of length
l_q bits. Decryption requires 1 exponentiation modulo m.
For comparison, Elgamal or standard DHAES in Z*_p requires 2
modexps for encryption (both of which can be precomputed,
one of which, unlike this scheme, has a fixed base, and
neither of which use short exponents), and 1 modexp for
decryption.
In other words, the efficiency is on balance roughly equal to
(or slightly better than, because the effect of the short
exponents will probably outweigh the extra modexp) Elgamal
or DHAES in Z*_p, for p about the same length as m.
Security:
For an attacker,
- without knowing the factorisation of m, a square root attack
in the subgroup generated by alpha seems to require O(sqrt(q))
work (which unlike the previously discussed Maurer-Yacobi
approaches, can be made arbitrarily more difficult than key
pair generation, by increasing r).
- a general discrete log attack is as hard as factoring m, by
Shmuely's result [Shmuely] (but note that this does not take
into account the fact that we have chosen a subgroup with a
particular structure).
- factoring m using the p-1 method is infeasible because the z_i
are not smooth, and so each p_i - 1 must have at least one
large factor. Other special-purpose factoring algorithms don't
appear to have any greater chance of working than normal.
- factoring m using ECM is infeasible as long as min[p_i: i = 1..r]
is large enough.
- factoring m using a general method is infeasible as long as m
is large enough.
Open questions:
- Does the structure of the chosen subgroup (in particular,
the fact that its order q is a smooth integer) allow a
more efficient discrete log attack?
- What is a reasonable minimum size for each of the q_i?
(This determines how efficient key pair generation can
be.)
- Neither the public key nor the private keys include q
(because it is not strictly needed for encryption or
decryption), but does the security of the scheme depend
on that?
[Note that if q were known, it could be factored easily into
the q_i. However, calculating the discrete log during key
pair generation *appears* to also require the z_i, which
can't be inferred from the q_i without factoring m.
What is the usual algorithm for computing discrete logs in
this case (i.e. in a subgroup of composite order), anyway -
is it the same method I've used?
[HAC] section 3.6.3, on Pollard rho, says:
# For simplicity, it is assumed in this subsection that
# G is a cyclic group whose order n is prime.
which is not very helpful.]
- What can the attacker infer from h and y?
- Can any extra information be inferred by knowing some of
the private values x_t?
- What should the range of k (the ephemeral exponent) be?
- Can this scheme be proven secure under reasonable
assumptions (perhaps by adapting the proofs in [DHAES]
and [Shmuely])?
Other applications:
The discrete log problem is the basis of many PK protocols
other than encryption, and some of these might benefit from
a forward-secrecy or forward-security property. (Each protocol
would have to be adapted slightly to work in a subgroup of
Z*_m.) For example, [FSIG] describes a forward-security
property for signatures, such that it is not possible to
forge a signature with a "time stamp" corresponding to a
private key that has been deleted. An alternative to the
algorithm described there would be to use this scheme as
the basis for creating private keys for a discrete log-based
signature algorithm, such as DSA or p-NEW.
Unlike FSIG, in this scheme private keys are computed from
the corresponding public keys directly, rather than applying
a one-way function to an "old" key to get the next key in
sequence. This has the disadvantage that the private key must
be larger, but the advantage that it is possible to store
future private keys off-line, where they are possibly less
vulnerable to compromise. (For an FSIG-like scheme there
would be no point in doing this, because future private keys
can be inferred from current ones.)
Miscellaneous:
The name of this algorithm is MYH, or Maurer-Yacobi-Hopwood.
(The notation (m, y, h, ...) for the public key is not entirely
a coincidence.)
To refer to an instantiation of MYH with specific algorithms, use
"MYH(H,F,SYM,MAC[,eLen[,mLen]])", for example
MYH(SHA-1,MGF1,Rijndael,HMAC,256,128)
(The hash used for MGF1 and HMAC would also be SHA-1 in this case.)
As far as I know, an implementation of this scheme would not
infringe on any patents provided the algorithms for H, F, SYM and
MAC do not.
References:
[DHAES] Michel Abdalla, Mihir Bellare, Phillip Rogaway,
"DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem,"
Contribution to IEEE P1363a.
http://grouper.ieee.org/groups/1363/contributions/dhaes.pdf
(temporary URL), or
Theory of Cryptography Library.
http://philby.ucsd.edu/cryptolib/1999/99-07.html
[P1363] (Draft) Standard for Public-Key Cryptography,
http://stdsbbs.ieee.org/groups/1363/index.html
[HAC] A. Menezes, P.C. van Oorschot, S.A. Vanstone,
Handbook of Applied Cryptography, CRC Press, 1997.
http://www.cacr.math.uwaterloo.ca/hac/about/chap<n>.pdf
where <n> is the chapter number.
[Pollard] J.M. Pollard,
"Monte Carlo methods for index computation (mod p),"
Mathematics of Computation, 32 (1978), 918-924.
[MY96] Ueli M. Maurer, Yacov Yacobi,
"A Non-interactive Public-Key Distribution System,"
Designs, Codes and Cryptography, 1996.
http://www.inf.ethz.ch/personal/maurer/publications.html
ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/dcc.ps
[Shmuely] Z. Shmuely,
"Composite Diffie-Hellman public-key generating systems
are hard to break,"
TR 356, CS Dept., Technion, Israel, Feb. 1985.
[FSIG] Mihir Bellare, Sara K. Miner,
"A Forward-Secure Digital Signature Scheme,"
July 13, 1999.
Extended abstract: Advances in Cryptology - Crypto '99
Proceedings, LNCS Vol. 1666, M. Wiener ed., Springer-Verlag, 1999.
Full version: http://www-cse.ucsd.edu/users/mihir/papers/fsig.html
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOIVm9jkCAxeYt5gVAQFfJAgAj6DGpyRw67y04VcWQe48QFyfr3ygDshw
VzU+6Ds9Eb67Od3aMWXAuNF7a1nFtraeqN/lAT7JPd+mkQdi/0Bs+BRp36/c4zDm
6dM+XjASCVA/tRqJhozjESebp4SNAcvv3a/ipbvMTbp4XveT0ldtR/If7LDTJDz4
LzJ6ah5IPGBRC8CZQhHuccfVFMuJPtPoIhyK/HvsqoiP9F8SY3MdOph5TBcSRfdl
pa45foPiF102j1ryyC5yTiINozE7AnYZ7dPwJtBQrBP3IFfSY8KXpYjRFnviZbQs
OrfOusrngW4mOOTWwZrGmuEYYXqE0ehXY62bN4sJMmIxH+NfelNk9w==
=Lu9G
=====END PGP SIGNATURE=====
------------------------------
From: "Artemios G. Voyiatzis" <[EMAIL PROTECTED]>
Subject: Re: Java's RSA implimentation
Date: Wed, 19 Jan 2000 09:52:19 +0200
Greeting to all,
Java2 provides the package java.math.BigInteger for big integer arithmetic.
In this package there all almost all the routines you may need to implement
cryptographic algorithms.
There is a constructor BigInteger(int bitLength, int certainty, Random rnd)
which constructs a BigInteger with "bitLength" length in bits and that is
probably prime, with probability (1/2)^certainty that is composite.
There is also a method in this package, isProbablePrime(int certainty),
which
"Returns true if this BigInteger is probably prime, false if it's definitely
composite."
according to Java2 API Documentation
(http://www.javasoft.com/products/jdk/1.2/docs/api/index.html)
The primality tests are a mix of typical primality tests and a set of
Monte-Carlo algorithms. As I have seen in
the sources, the package is implemented as native methods (in C and assembly
based on my Solaris sources of Java2),
so they provide comparable speed with that of a plain-C implementation.
I think the author of this package is Colin Plumb and the implementation was
based on Knuth's
books and academic bibliography for efficient big integer arithmetic, if of
any interest.
Hope this was useful,
Artemios G. Voyiatzis
"Science is what we understand
well enough to explain to a computer.
Art is everything else"
(Donald Erwin Knuth)
"Bill Unruh" <[EMAIL PROTECTED]> wrote in message
news:863m2q$abe$[EMAIL PROTECTED]...
> In <862upd$vr$[EMAIL PROTECTED]> [EMAIL PROTECTED] writes:
>
> >Is anyone aware of any effort to analyse the RSA implementation in Java;
> >specifically focusing on key generation.
>
> ??? Java is a language, much like C in many essentials. It is up to you
> to code what you want it to do.
>
> >Does Java use a table of primes? If so, how big is the table?
>
> No, Java does not. But you can enter a table of primes if you wish. And
> you can encode a prime testing routine in Java just as you can in C.
>
> >Otherwise how good is it's prime number generation routines ie. what is
> >the probability of a generated number not being prime.
>
> I do not know that Java has a "prime number generating routine". but you
> can code one up in Java.
> Jus tread the code in any RSA implimentation.
>
>
> >Thanks.
>
>
> >Sent via Deja.com http://www.deja.com/
> >Before you buy.
------------------------------
** 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
******************************
