High-Speed Algorithms for RSA Cryptograms

Yasushi Fuwa

Shinshu University, Nagano

Yoshinori Fujisawa

Shinshu University, Nagano

Summary.

In this article, we propose a new high-speed processing method for encoding and decoding the RSA cryptogram that is a kind of public-key cryptogram. This cryptogram is not only used for encrypting data, but also for such purposes as authentication. However, the encoding and decoding processes take a long time because they require a great deal of calculations. As a result, this cryptogram is not suited for practical use. Until now, we proposed a high-speed algorithm of addition using radix-$2^k$ signed-digit numbers and clarified correctness of it ([6]). In this article, we defined two new operations for a high-speed coding and encoding processes on public-key cryptograms based on radix-$2^k$ signed-digit (SD) numbers. One is calculation of $(a*b)$ mod $c$ ($a,b,c$ are natural numbers). Another one is calculation of $(a^b)$ mod $c$ ($a,b,c$ are natural numbers). Their calculations are realized repetition of addition. We propose a high-speed algorithm of their calculations using proposed addition algorithm and clarify the correctness of them. In the first section, we prepared some useful theorems for natural numbers and integers and so on. In the second section, we proved some properties of addition operation using a radix-$2^k$ SD numbers. In the third section, we defined some functions on the relation between a finite sequence of k-SD and a finite sequence of ${\Bbb N}$ and proved some properties about them. In the fourth section, algorithm of calculation of $(a*b)$ mod $c$ based on radix-$2^k$ SD numbers is proposed and its correctness is clarified. In the last section, algorithm of calculation of $(a^b)$ mod $c$ based on radix-$2^k$ SD numbers is proposed and we clarified its correctness.

MML Identifier: RADIX_2

Contents (PDF format)

1. Some Useful Theorems
2. Properties of Addition Operation Using Radix-$2^k$ Signed-Digit Numbers
3. Definitions on the Relation Between a Finite Sequence of $k$-SD and a Finite Sequence of ${\Bbb N}$ and Some Properties about them
4. A High-Speed Algorithm of Calculation of $(a*b)$ mod $b$ Based on Radix-$2^k$ Signed-Digit Numbers and its Correctness
5. A High-Speed Algorithm of Calculation of $(a^b)$ mod $b$ Based on a Radix-$2^k$ Signed-Digit Numbers and its Correctness

Bibliography

[1] Grzegorz Bancerek. The fundamental properties of natural numbers. Journal of Formalized Mathematics, 1, 1989.

[2] Grzegorz Bancerek. Joining of decorated trees. Journal of Formalized Mathematics, 5, 1993.

[3] Grzegorz Bancerek and Krzysztof Hryniewiecki. Segments of natural numbers and finite sequences. Journal of Formalized Mathematics, 1, 1989.

[4] Czeslaw Bylinski. Functions and their basic properties. Journal of Formalized Mathematics, 1, 1989.

[5] Czeslaw Bylinski. The sum and product of finite sequences of real numbers. Journal of Formalized Mathematics, 2, 1990.

[6] Yoshinori Fujisawa and Yasushi Fuwa. Definitions of radix-$2^k$ signed-digit number and its adder algorithm. Journal of Formalized Mathematics, 11, 1999.

[7] Krzysztof Hryniewiecki. Basic properties of real numbers. Journal of Formalized Mathematics, 1, 1989.

[8] Andrzej Kondracki. The Chinese Remainder Theorem. Journal of Formalized Mathematics, 9, 1997.

[9] Takaya Nishiyama and Yasuho Mizuhara. Binary arithmetics. Journal of Formalized Mathematics, 5, 1993.

[10] Andrzej Trybulec. Tarski Grothendieck set theory. Journal of Formalized Mathematics, Axiomatics, 1989.

[11] Andrzej Trybulec. Subsets of real numbers. Journal of Formalized Mathematics, Addenda, 2003.

[12] Michal J. Trybulec. Integers. Journal of Formalized Mathematics, 2, 1990.

[13] Wojciech A. Trybulec. Pigeon hole principle. Journal of Formalized Mathematics, 2, 1990.

[14] Zinaida Trybulec. Properties of subsets. Journal of Formalized Mathematics, 1, 1989.