HOME

TheInfoList



OR:

The Okamoto–Uchiyama cryptosystem is a public key cryptosystem proposed in 1998 by Tatsuaki Okamoto and Shigenori Uchiyama. The system works in the
multiplicative group of integers modulo n In modular arithmetic, the integers coprime (relatively prime) to ''n'' from the set \ of ''n'' non-negative integers form a group under multiplication modulo ''n'', called the multiplicative group of integers modulo ''n''. Equivalently, the el ...
, (\mathbb/n\mathbb)^*, where ''n'' is of the form ''p''2''q'' and ''p'' and ''q'' are large primes.


Background

Let p be an odd prime. Define \Gamma = \. \Gamma is a subgroup of (\mathbb/p^2 \mathbb)^* with , \Gamma, = p (the elements of \Gamma are 1, 1+p, 1+2p \dots 1 + (p-1)p). Define L: \Gamma \to \mathbb/p\mathbb by L(x) = \frac L is a homomorphism between \Gamma and the additive group \mathbb/p\mathbb: that is, L(ab) = L(a) + L(b) \bmod p. Since L is bijective, it is an isomorphism. One can now show the following as a corollary: Let x \in \Gamma such that L(x) \neq 0 \bmod p and y = x^m \bmod p^2 for 0 \leq m < p. Then : m = \frac = \frac \bmod p The corollary is a direct consequence of L(x^m) = m \cdot L(x).


Operation

Like many public key cryptosystems, this scheme works in the group (\mathbb/n\mathbb)^*. This scheme is homomorphic and hence
malleable Ductility refers to the ability of a material to sustain significant plastic deformation before fracture. Plastic deformation is the permanent distortion of a material under applied stress, as opposed to elastic deformation, which is reversi ...
.


Key generation

A public/private key pair is generated as follows: # Generate two large primes p and q. # Compute n = p^2 q. # Choose a random integer g \in \ such that g^ \not\equiv 1 \mod p^2. # Compute h = g^n \bmod n. The public key is then (n,g,h) and the private key is (p,q).


Encryption

A message m < p can be encrypted with the public key (n,g,h) as follows. # Choose a random integer r \in \. # Compute c = g^m h^r \bmod n. The value c is the encryption of m.


Decryption

An encrypted message c can be decrypted with the private key (p,q) as follows. # Compute a = L(c^ \bmod). # Compute b = L(g^ \bmod). a and b will be integers. # Using the
Extended Euclidean Algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's id ...
, compute the inverse of b modulo p: #:b' = b^ \bmod p. # Compute m = ab' \bmod p. The value m is the decryption of c.


Example

Let p = 3 and q = 5. Then n = 3^2 \cdot 5 = 45. Select g = 22. Then h = 22^ \bmod 45 = 37. Now to encrypt a message m = 2, we pick a random r = 13 and compute c = g^m h^r \bmod n = 22^ 37^ \bmod 45 = 43. To decrypt the message 43, we compute : a = \frac = 1. : b = \frac = 2. : b' = 2^ \bmod 3 = 2. And finally m = ab' = 2.


Proof of correctness

We wish to prove that the value computed in the last decryption step, ab' \bmod p, is equal to the original message m. We have :(g^mh^r)^ \equiv (g^m g^)^ \equiv (g^)^m g^ \equiv (g^)^m \mod p^2 So to recover m we need to take the
discrete logarithm In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...
with base g^. This can be done by applying L, as follows. By
Fermat's little theorem In number theory, Fermat's little theorem states that if is a prime number, then for any integer , the number is an integer multiple of . In the notation of modular arithmetic, this is expressed as a^p \equiv a \pmod p. For example, if and , t ...
, g^ \equiv 1 \bmod p. Since g^ \not\equiv 1 \bmod p^2 one can write g^ = 1 + pr with 0 < r < p. Then L(g^) \not\equiv 0 \bmod p and the corollary from earlier applies: m = \frac \bmod p.


Security

Inverting the encryption function can be shown to be as hard as factoring ''n'', meaning that if an adversary could recover the entire message from the encryption of the message they would be able to factor ''n''. The
semantic security In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any probabilistic, polynomial-time algorithm (PPTA) that is given the ci ...
(meaning adversaries cannot recover any information about the message from the encryption) rests on the ''p''-subgroup assumption, which assumes that it is difficult to determine whether an element ''x'' in (\mathbb/n\mathbb)^* is in the subgroup of order ''p''. This is very similar to the
quadratic residuosity problem The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not. Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which a ...
and the higher residuosity problem.


References

* {{DEFAULTSORT:Okamoto-Uchiyama cryptosystem Public-key encryption schemes