High-speed algorithms for RSA cryptograms
Yasushi Fuwa · Formalized Mathematics · 2001
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 highspeed algorithm of addition using radix-2 signed-digit numbers and clarified correctness of it ([5]). In this article, we defined two new operations for a highspeed coding and encoding processes on public-key cryptograms based on radix2 signed-digit (SD) numbers. One is calculation of (a∗b) mod c (a, b, c are natural numbers). Another one is calculation of (a) 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 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 N and proved some properties about them. In the fourth section, algorithm of calculation of (a ∗ b) mod c based on radix-2 SD numbers is proposed and its correctness is clarified. In the last section, algorithm of calculation of (a) mod c based on radix-2 SD numbers is proposed and we clarified its correctness.