The memo that I studied. There weren't many articles about implementing RSA that works well with large prime numbers.
Implement 256bit RSA encryption with the minimum configuration.
See wikipedia for details, and write only the flow.
Now you are ready. Encryption is
Decryption is OK with $ m = c ^ d \ pmod n $.
There is no such difficult calculation, but the point is
--Exponentiation is heavy ――How to make big prime numbers $ p, q $? -How do you decide $ e $? --What about $ d $?
In RSA, powers are multiplied by hundreds of digits, so exponential multiplication cannot be done obediently.
** Fast exponential operation ** makes it faster.
Furthermore, since what we want to find is the surplus of the power, not the power itself, we can optimize this point as well.
Let's say you want to calculate the remainder of $ a $ raised to the $ b $ power by $ n $. First, convert $ b $ to a binary number. Let each digit of the binary number be $ b_i $
As
Divide each by $ 21 $ and take too much if it exceeds 21 during the calculation.
main.py
def modular_exp(a, b, n):
res = 1
while b != 0:
if b & 1 != 0:
res = (res * a) % n
a = (a * a) % n
b = b >> 1
return res
Apparently it's quite difficult to generate prime numbers directly. Practically, it seems easy to ** generate random numbers until they hit a prime number **.
Since the number of bits is specified, it is OK if 0,1 are randomly arranged for that number.
main.py
def gen_rand(bit_length):
bits = [random.randint(0,1) for _ in range(bit_length - 2)]
ret = 1
for b in bits:
ret = ret * 2 + int(b)
return ret * 2 + 1
The maximum bit and the minimum bit are set to 1 instead. This is because the maximum bit is an odd number so that the number of digits is not reduced. The reason for odd numbers is that I want prime numbers now, and even numbers are not prime numbers.
I want to determine if the huge random number $ p $ is a prime number. $ P $ is so big that it's too slow to divide it in order. ** [Miller-Rabin Primality Test](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3% 83% A9% E3% 83% 93% E3% 83% B3% E7% B4% A0% E6% 95% B0% E5% 88% A4% E5% AE% 9A% E6% B3% 95) ** Seems to be often used. The algorithm is also on wikipedia, so implement it as it is. Simply put, we check the requirements for prime numbers many times and determine that if they all pass, they are probably prime numbers, and if they don't pass even one, they are composite numbers. ** Since this is a probable primality test algorithm, composite numbers may be judged as prime numbers. ** ** However, it seems that the false positive is about $ \ frac {1} {4} $ in one check, so if you do it dozens of times, it will be almost 0 in practical use, so there seems to be no problem.
main.py
def mr_primary_test(n, k=100):
if n == 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
d = n - 1
s = 0
while d % 2 != 0:
d /= 2
s += 1
r = [random.randint(1, n - 1) for _ in range(k)]
for a in r:
if modular_exp(a, d, n) != 1:
pl = [(2 ** rr) * d for rr in range(s)]
flg = True
for p in pl:
if modular_exp(a, p, n) == 1:
flg = False
break
if flg:
return False
return True
So, prime number generation is like this.
main.py
def gen_prime(bit):
while True:
ret = gen_rand(bit)
if mr_primary_test(ret):
break
return ret
It is quick to make it a prime number because it can be relatively prime with $ (p-1) (q-1) $.
p = gen_prime(128)
q = gen_prime(128)
e = gen_prime(128)
I think there is no problem with that. wikipedia states that $ 65537 $ is often used. It seems that a fixed constant is fine.
You can use the extended Euclidean algorithm.
Originally for natural numbers $ a, b $
It is an algorithm to find $ x, y $ such that. (gcd is the greatest common divisor)
Use this for $ e, (p-1) (q-1) $. Since the greatest common divisor is 1 from the definition of $ e
Dividing both sides by $ (p-1) (q-1) $
main.py
def xgcd(b, n):
x0, x1, y0, y1 = 1, 0, 0, 1
while n != 0:
q, b, n = b // n, n, b % n
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return b, x0, y0
def gen_d(e, l):
_, x, _ = xgcd(e, l)
return x % l
The rest will work if you prepare plaintext.
main.py
bit_length = 128
p = gen_prime(bit_length)
q = gen_prime(bit_length)
e = gen_prime(bit_length)
d = gen_d(e, (p - 1) * (q - 1))
n = p * q
m = 123456789
c = modular_exp(m, e, n) #Cryptogram
m_ = modular_exp(c, d, n) # 123456789
It worked even with 1024bit. (It took about 20 seconds) Actually, it is dangerous to encrypt the same plaintext many times, so it seems that a random number is added at the end (deleted at the time of decryption), and if m is too small, it is padded.