RU2071180C1 - Public-key method for message encryption and device which implements said method - Google Patents

Abstract

FIELD: devices for communications, computer engineering. SUBSTANCE: digital signal of encrypted message B is generated by means of raising digital signal of source message A to open power e by module m which is product of two private primes p and q $$$ Then encrypted message is sent to receiver and is decoded by means of private key. Private exponent S for decoding conforms to equation $$$, while (p-1) is relatively prime. Rest of decoded message $$$ is generated during decoding by means of equation $$$ = B mod p. Then, digital signal of decoded message is generated by means of equation $$$. Corresponding device has encoding unit 1, transmission line 2, decoding unit 3, rest generation unit 4, unit 5 which generates decoded message. EFFECT: increased speed. 2 cl, 1 dwg

Description

 The invention relates to communications and computer technology and is intended to ensure the confidentiality of messages sent along message lines.

 A known method of encrypting messages with a public key is when the sender of the message encrypts it with an open, public key and sends the encrypted message to the recipient. The recipient decrypts the received message with a secret, only known key [1]. In the known method, the original and encrypted message is formed as digital integers as large integers, and all actions on digital signals are performed in the form of calculations on integers.

As part of the public key, the number m-module and the e-open exponent are specified. To force a digital signal of an encrypted message, the operation of raising the original digital message A to a power modulo m is implemented:
B = A ^e mod m, (1)
where is the encrypted message.

The encrypted message is forwarded to the recipient. The formation of the digital signal of the decrypted message is performed as raising the received encrypted message B _t to the power S modulo m:
A _t = B $\genfrac{}{}{0ex}{}{\text{S}}{\text{t}}$ modm, (2)
where A _t decrypted message,
S is a secret exponent that is part of the secret key.

 The disadvantage of this method is the insufficiently fast decryption process.

 Encryption in the known method is performed quickly, since the open exponent e is chosen small. Decryption for large multi-digit numbers is very slow. Sometimes m is represented as the product of two large primes p and q.

In this case, instead of a direct calculation by formula (2), the decrypted message is formed in parts using the Chinese remainder theorem. To do this, pre-calculate the inversion of the 1st prime number modulo the 2nd according to the ratio:
(r • q mod q 1 (3)
where r is the inverse.

A_t (((A₂ A₁) • r)vodq) • p + A₁ (8)
где S₁, S₂ 1-й и 2-й остатки секретного показателя степени, А₁, A₂ 1-й и 2-й остатки сообщения, А_t - дешифрованное сообщение.The inversion is calculated by the generalized Euclidean algorithm for GCD (the largest common divisor). Then decryption is carried out by carrying out the following calculations:
S ₁ Smod (p 1), (4)
S ₂ Smod (q 1), (5)

A _t (((A ₂ A ₁ ) • r) vodq) • p + A ₁ (8)
where S ₁ , S ₂ 1st and 2nd remnants of the secret exponent, A ₁ , A ₂ 1st and 2nd remnants of the message, And _t - decrypted message.

The most time-consuming here are raising to a degree modulo (6), (7), the remaining actions are performed hundreds of times faster. When directly raising to a power modulo by formula (2), the length of all numbers: B _t , S _u , A _t are n bits. The calculation time for large n is proportional to n ³ . When calculated by formulas (3) (8), the lengths of the numbers p, q, r, S ₁ , S ₂ , A ₁ , A ₂ are n / 2 bits, so these two exponents to a power modulo compute 4 times faster than one in (1).

The closest technical solution is the method of encrypting messages with a public key, using the RSA method that implements two functions: encryption of messages with a public key and electronic signing [2]
The encryption function is implemented as follows. The public key contains a pair of integers: the module and the public exponent e. The module m must be equal to the product of two secret primes p and q. The open exponent e is chosen small to save calculations, and e must satisfy the ratio:
GCD (e, (p 1) • (q 1) 1, (9)
where gcd is the largest divisor.

The secret text contains another (secret) exponent S calculated as the inverse of e modulo ((p 1) •) (q 1)):
(S • e) mod ((p 1) • (q 1)) 1 (10).

During encryption, a number A is raised to a power of e modulo m according to formula (1), as a result of which an encrypted message B is received, which is sent along the message line to the recipient. The recipient decrypts the received message B _t by raising the number B _t to the power S modulo m according to the formula (2) or (3) 8). If there was no distortion in the transmission of the encrypted message (B _t B), then due to the identity
A ^{(p - 1)} • ^{(q - 1)} mod (p • q) 1 (11)
decrypted message will match the original message
^{_{A t (A s modm) e}} modm A se modm A ^{to (p - 1) (q - 1) +1} modm A
Encryption in the known method according to the formula (1) is carried out quickly, usually in fractions of a second, since the length of the open exponent is of the order of 3-5 bits. However, decryption by formulas (2) or (3) (8) is tens of seconds for microprocessors. The main disadvantage of the RSA method is the large decryption time.

 EFFECT: accelerated decryption process and increased encryption reliability.

 In the presented method, a digital signal of an encrypted message is generated from the original message with a public key, then a digital, encrypted message is sent along the message line, and then a digital signal of the decrypted message is generated with a secret key.

The open exponent e for encryption is chosen so that (p 1) and e are mutually simple, the secret exponent S for decryption is determined according to the ratio:
(S • e) mod (p 1) 1 (12)
and decryption is performed by forming the remainder of the received decrypted message B _t modulo p:
B ₁ B _t modp (13)
and raising the remainder of B ₁ to a secret degree S
A _t B ₁ modp (14)
If the sent and received messages coincide (B _t B), the decrypted message A _t will be equal to the original message due to the identity
A ^{p - 1} modp 1 (15)
Indeed, taking into account (12):
A _t ((A ^e modm) modp) ^s modp A ^es modp A ^{k (p-1) +1} modp A
For high reliability, the length of the numbers n should be on the order of 500 1000 bits.

 Thus, instead of two n / 2-digit exponents, only one remains during decryption. Therefore, in the present method, in comparison with the RSA method, decryption is doubled with the same reliability.

 In FIG. 1 is a block diagram of a public key message encryption system.

 The public key message encryption system comprises an encryption block, a message transmission line 2, a decryption block 3, comprising a sub-block 4 for generating the remainder of the received encrypted message, a sub block 5 for generating the decrypted message.

 The public key message encryption system operates as follows.

The encryption block 1 receives the initial message A and the public key containing the product of two secret numbers m and the public exponent e. Message B encrypted in block 1 using formula (1) is sent from it to message transmission line 2. A secret key containing a secret 1st prime number and a secret metric goes to subblocks 4 and 5 of block 3 in the following order: secret 1st prime P to subblocks 4 and 5, a secret metric S to subblock 5. From transmission line 2 of messages, the received encrypted message B _t enters sub-block 4 of block 3, which is formed in accordance with formula (13) and the remainder of the received encrypted message B ₁ goes to sub-block 5 of block 3. The decrypted message A _t generated in sub-block 5 by formula (14) is output system.

Claims (2)

1. A method of encrypting messages with a public key, including generating a digital signal of an encrypted message B from a digital signal of the original message A using a public key according to the formula
BA ^e mod m,
where e is an open exponent,
mp • q, where p, q are secret primes,
moreover, e and m form the public key, transmitting the encrypted message on the transmission line and then decrypting the received encrypted message B _t using the secret key, characterized in that as the open exponent e, choose a number that is coprime to the number p 1, the secret exponent S is chosen according to the ratio
(S • e) mod (p 1) 1,
decryption is carried out by forming the remainder B _{1 of the} received encrypted message B _t according to the formula
B ₁ B _t mod p
and forming a decrypted message A _t according to the formula
A _t = B $\genfrac{}{}{0ex}{}{\text{S}}{\text{1}}$ modp
where s and p form a secret key. 2. The public key message encryption system, containing a series-connected encryption unit that generates an encrypted message according to the formula
b A ^e mod m,
a message line and a decryption unit, characterized in that the decryption unit contains a series-connected subunit for generating the remainder of the received encrypted message according to the formula
B ₁ B _t mod p,
and a sub-block for generating a decrypted message according to the formula
A _t = B $\genfrac{}{}{0ex}{}{\text{S}}{\text{1}}$ modp.