Okamoto–Uchiyama cryptosystem
Okamoto - Uchiyama, the cryptosystem is semantically secure an asymmetric encryption algorithm. It was first presented by Okamoto and Shigenori Uchiyama Tatsuaki at Eurocrypt, one of the largest annual conferences cryptography in 1998. The process is additive - homomorphic, meaning that the plaintexts are added by the multiplication of two key texts. It is therefore not necessary to decrypt the key texts in order to operate on the plaintexts can.
- 4.1 advantages
- 4.2 disadvantages
- 5.1 Key Generation
- 5.2 Preliminary
- 5.3 encryption
- 5.4 decryption
Method
How many asymmetric encryption methods, the Okamoto - Uchiyama cryptosystem works in the group. However, the module is used in contrast to other methods, such as RSA, of the mold, large prime numbers. The method being homomorphic and therefore suffers from the associated problems.
Generation of public and private key
The key pair is generated as follows:
- It generates two primes of the same bit length, and sets. In practice, should be at least 1024, but have better 1536 or 2048 binary digits.
- It randomly chooses in order so has.
- We define
The public key consists of the private key from.
Encrypting messages
To encrypt a message, the procedure is as follows:
- First you choose a random.
- The encrypted message is then given by.
Decrypt messages ( decoding)
To decrypt first defined the function. Then we obtain the original message follows:
- One defines.
- Man sets.
In the last step is to be noted that the modulo division needs to be performed, i.e., . By multiplication by the multiplicative inverse The division in the calculation is performed over the integers.
Correctness of the Okamoto - Uchiyama cryptosystem
For an odd prime p we define the group of as
That is, contains exactly those elements of that supply through the rest of 1 when divided.
Then one defines the logarithmic function on the elements of the
This value is always an integer, as is true for all that.
It now applies.
Proof:
The first equation holds because. The last equation holds since valid according to the above observation.
If now is for one that, and furthermore, for a, we obtain further
In this respect also the reason for the name is logarithmic function, since the discrete logarithm of is calculated in basis.
Proof: This follows trivially from the previous property for, and applies.
From this there follows the overall correctness of the method, ie, that
Actually coincides with the original message.
Proof: We first observe that
Was being used for the last equation of the set of Lagrange. We then get:
Important here is that, and was also fulfilled, since, by assumption, was a number with k bits in length.
Security
Of the p- sub-groups assumption it can be shown that the method is semantically secure. The inverting the encryption is proven to be just as complex as the factorization of the module.
Homomorphieeigenschaften
As with all homomorphic encryption method, an attacker can modify a ciphertext so that it is decrypted to a related to the original plaintext plaintext. For example, let the encryption of an unknown value. Then can very easily be changed to any value by multiplication with the encrypted value:
In a similar way one can also unknown plaintext with any factor multiplied by the exponentiated ciphertext:
However, in order to achieve a reasonable result here (for example, a doubling of the plaintext ) must be guaranteed, that is true, or even, so that the receiver from the decryption can not draw any conclusions on the manipulation (all correctly encrypted plaintexts may yes its maximum bits long according to regulations ).
Benefits
The homomorphic properties are exploited among others in connection with the following applications.
- E- Voting: After every voter his voice (in the simplest case, a 1 for yes, 0 for no) is encrypted and transmitted to the electoral authority, all ciphertexts are multiplied, and the resulting encryption, the encryption of the total number of votes in favor. Is now obtained by decrypting the election results. It is important that the first step performing party does not require any knowledge of the secret key, whereby no individual voices can be decrypted.
- eCash
- Zero-knowledge proofs in the Universal Composability model
Disadvantages
Because of the listed Homomorphieeigenschaften the method is, however, not IND -CCA secure, that is not safe under chosen ciphertext attacks. Each encryption system that owns this security should in fact non- deformable be, a property which is in contradiction to the homomorphism. In the literature, there are also transformations to transform the system into an IND -CCA secure variant. If these transformations are attached or not, depends on the particular application.
Complete Example
The above steps will be illustrated here with a simple example.
Key generation
First of two secret prime numbers are chosen as an example. Both have 10 bits in the binary representation, that is, it is. This results in further:
The supplies incidental, appropriate choice of
- , Where and are valid.
The public key is thus given by:
The secret key is.
Preparatory work
In a first step, the text to be encrypted must be smaller than translated into numbers. We simply replace each letter to its position in the alphabet:
A = 01 B = 02 C = 03, etc. (00 = space ) We now individually encrypt each character as two consecutive letters may could provide too large a value.
Plaintext: O U K Encoding: 15 21 11 encoding
We have three plaintexts to be encrypted plaintexts ( and ) for which we need one.
R1 = 523 423 432 r2 = 43,412,311 r3 = 633 186 663 The encryption result is then:
Ci = gmihri mod n c1 = 33,270,615 = 289 652 071 916 872 763 344141213523423432 mod c2 = 423 840 839 c3 = 684 226 192 decryption
We can decrypt the message by:
Mi = L ( cip - 1 mod p2 ) / L ( gp ) mod p Important here is that the division is performed. We therefore calculated using the extended Euclidean algorithm, the multiplicative inverse of modulo, and get it. Thus, the decoding results for:
M1 = L ( mod 2896520711018 1038361 ) * 502 mod 1019 = 15 m2 = 21 m3 = 11 By inverting the substitution rule, these values can be translated into letters again.
Swell
- Asymmetric encryption algorithm