RSA暗号をpythonで実装してみた（車輪の再発明）

RSA暗号を実装しみてる

半年前にRSA暗号勉強したのですが、ほぼほぼ忘れてしまっていました...

記憶力悲しき。

RSA暗号を忘れないように、今回はちゃんと記事として置いておこうと。

人様に公開するような内容ではありません。

参考記事

非理系が学ぶなら、このサイトがおすすめ。

RSA暗号の世界 – まいとう情報通信研究会

コードを書くときに参考にしました。

qiita.com

コード

import random


def gcd(a, b):
	# 最大公約数を求める
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
	# 最小公倍数を求める
	return a * b // gcd (a, b)

def generate_keys(p, q):
	# 与えられた2つの素数pとqから秘密鍵と公開鍵を生成する

	pq = p * q
	period = lcm(p - 1, q -1)

	#公開鍵の候補をリストに入れる
	#period = lcm(p - 1, q -1)の中にある素数をappned
	prime_number_list = []
	for i in range(2, period):
		if gcd(i, period) == 1:
			prime_number_list.append(i)

	#ランダムでpublic keyを抽出
	public_key = random.choice(prime_number_list)

	#秘密鍵を生成
	secret_key = 1
	n = 1
	while True:
		# 乗算したら元に戻る数値を探す
		# (A3)D = A{n × (P – 1) × (Q – 1) + 1}
		if secret_key * public_key == n * period + 1:
			break

		# secret_key * public_keyがn * period + 1より大きくなった場合は、nにプラス1
		if secret_key * public_key > n * period + 1:
			n += 1

		secret_key += 1 

	return [public_key, secret_key, pq]


def encrypt(plain_text, public_key, law):
	# 公開鍵を使って、プレーンテキストを暗号化
	encode_text =  [ord(char) for char in plain_text]
	encrypt_text = [i ** public_key % law for i in encode_text]
	encrypt_text_join = "".join(chr(i) for i in encrypt_text)

	return encrypt_text_join


def dencrypt(encrypt_text, secret_key, law):
	# 暗号化されたテキストの解読
	encode_text = [ord(char) for char in encrypt_text]
	dencrypt_text = [i ** secret_key % law for i in encode_text]
	dencrypt_text_join = "".join(chr(i) for i in dencrypt_text)

	return dencrypt_text_join


if __name__ == "__main__":
	text = "hello world"

	p = 101
	q = 3259

	public_key, secret_key, law = generate_keys(p, q)
	encrypt_text = encrypt(text, public_key, p*q)
	dencrypt_text = dencrypt(encrypt_text, secret_key, p*q)
	
	print("plain_text : ", text)
	print("encrypt_text : ", encrypt_text)
	print("dencrypt_text : ", dencrypt_text)