RSA暗号のpython実装

競プロとは関係ないですが。授業で聞いて面白かったので実装してみました。
アルゴリズムの解説

(準備)

1. 素数 を決める (十分大きな数)
2. を求め、 と互いに素な数 を1つランダムに選ぶ。
3. となる を求める。( の特殊解を求めることと同値 )

(暗号化)
平文 (数字) に対し、暗号 は で求める。

(復号化)
暗号 (数字) に対し、元の平文 は で求める。

(全体像)
公開鍵は、 と である。
が十分に大きい時、 から を求めることが現実的でないことを利用している。

from random import randint
class RSA:
	def __init__(self,p1,p2):
		self.__p1,self.__p2,self.__d,self.e,self.n = self.__makeKey(p1,p2)

	def __gcd (self,a,b):
		if a < b:
			a,b = b,a
		return a if b == 0 else self.__gcd(b,a%b)

	def __lcm (self,a,b):
		return a*b//self.__gcd(a,b)

	def __extended_euclid(self,a,b,k = 1):
		if k != 1:
			g = self.__gcd(a,b)
			a //= g
			b //= g

		cc = gg = 1
		ee = ff = 0
		while b:
			div,mod = divmod(a,b)
			hh = cc - div * ee
			ii = ff - div * gg
			a,b = b,mod
			cc,ee = ee,hh
			ff,gg = gg,ii

		return (cc,ff)

	def __choose_e(self,n,e = 0):
		if e != 0:
			return e
		while True:
			k = randint(n+100,n+1000)
			if self.__gcd(k,n) == 1:
				return k

	def __makeKey (self,p1,p2):
		n = p1*p2
		l = self.__lcm(p1-1,p2-1)
		e = self.__choose_e(l)
		(d,se) = self.__extended_euclid(e,l)
		if d <= 0:
			d += l 
		return p1,p2,d,e,n

        # 暗号化(数字)
	def encode (self,x):
		if x > self.n:
			print("x must be under {0}".forat(self.n))
			exit(1)
		return pow(x,self.e,self.n)
       # 復号化(数字)
	def decode (self,c):
		return pow(c,self.__d,self.n)
       # 暗号化(文字)
	def encode_str (self,s):
		ret = []
		for i in range(len(s)):
			ret.append(self.encode(ord(s[i])))
		return ret
        # 復号化(文字)
	def decode_str (self,s):
		ret = []
		for i in range(len(s)):
			ret.append(chr(self.decode(s[i])))
		return "".join(ret)

実行例

A = RSA(149,151) # 149 と 151

# 公開鍵
print (A.e,A.n)

# 数字の暗号化
Code = A.encode(57)
print(Code)

#数字の復号化
Raw = A.decode(Code)
print(Raw) # 57に戻る

#文字の暗号化
Code = A.encode_str("Hello")
print(Code)

#文字の復号化
Raw = A.decode_str(Code)
print(Raw) # "Hello"に戻る