• Sinh viên: Nguyễn Tú Anh
• MSV: A29888
• Trường: Đại học Thăng Long

• Môn học: Số học thuật toán
• Giảng viên: GS. Hà Huy Khoái
• Chủ đề: Mã hóa RSA
• Ngôn ngữ lập trình: Python
• Tài nguyên sử dụng: Tính toán trên số lớn có sẵn của python
• Nội dung chính: Mã hóa văn bản (Tiếng Việt có dấu) với RSA và khóa tự sinh (1024 bits)

MyMath.py: Chứa hàm toán học

• powMod(a, b, m): Trả về kết quả phép tính a^b mod m
• GCD(a, b):Trả về UCLN(a, b)
• GCD_extended(a, b): Trả về 3 số x,y,z thỏa mãn xa + yb = z = UCLN(a, b)

PrimeTest.py: Chứa hàm kiểm tra tính nguyên tố

• Preprocessor(a): Kiểm tra loại bỏ các số chia hết cho 1000 số nguyên tố đầu tiên (Tiền xử lý)
• Fermat(p,x): Kiểm tra số p sử dụng định lý Fermat nhỏ với x cơ sở
• Miller_Rabin(p, x): Kiểm tra Miller- Rabin với x cơ sở

GenePrime.py: Chương trình sinh nguyên tố xác suất

• Random (b): Hàm trả về số lẻ ngẫu nhiên b bits
• getPrime(b): Hàm trả về số nguyên tố xác suất b bits
• main(b): Hàm chạy chương trình sinh 2 số nguyên tố xác suất b bits

CreateKey.py: Tạo khóa cho mã hóa RSA

• getPQ(file): Lấy 2 số nguyên tố xác suất p q từ file
• getE(phi): Sinh số e là số nguyên tố cùng nhau với phi = (p-1)(q-1)
• getD(e, phi): Lấy số d là số nghich đảo mudulo của phi của e
• main(): Hàm chạy chương trình sinh khóa công khai(n,e) và khóa bí mật (n, d)

MyBase.py: Đổi cơ số

• toBase(a, base): Đổi từ số a cơ 10 sang cơ base
• toInt(r, base): Đổi từ số r cơ base sang cơ 10

encode.py: Chương trình mã hóa văn bản

• getPublicKey (file): Hàm lấy khóa công khai (n,e) từ file
• getPlaintext (file): Hàm lấy bản P rõ từ file
• convertStringToInt(P, base): Chuyển đổi các ký tự trong P thành số theo mã UTF- 8
• createBigInt(R, size_n): Ghép các số trong R với nhau thành 1 số có số các chữ số nhỏ hơn size_n
• encode(n, e, P, file): Mã hóa bản rõ P với khóa (n, e) lưu vào file với cơ 64
• main(): Hàm chạy chương trình mã hóa

decode.py: Chương trình giải mã văn bản

• getPrivateKey (file): Lấy khóa mật (n,d) từ file
• getCiphertext(file): Lấy văn bản mã hóa từ file
• decode(n, d, C, base, fileOut): Giải mã bản mã C xuất ra bản rõ vào fileOut
• main(): Chạy chương trình

• Ý nghĩa: Trả về kết quả phép tính a^b mod m

• Kiến thức: Bình phương liên tiếp

• Code:

  def powMod(a, b, m):
  	x = []
  	while b != 0:
  		x.append(b & 1)
  		b = b >> 1
  	sz = len(x)
  	po = [a%m]
  	for i in range(1,sz):
  		p = (po[i-1]*po[i-1])%m
  		po.append(p)
  	r = 1
  	for i in range(sz):
  		if(x[i] != 0):
  			r*= po[i]
  			r%= m
  	return r

• Ý nghĩa: Trả về UCLN(a, b)
• Kiến thức: UCLN(a, b)= UCLN(b, a% b), Giải thuật Euclid
• Code:

def GCD(a, b):
	if b == 0:
		return a
	return GCD(b, a%b)

• Ý nghĩa: Trả về 3 số x,y,z thỏa mãn x*a + y*b = z = UCLN(a, b)
• Kiến thức: Giải thuật Euclid mở rộng
• Code:

def GCD_extended(a, b):
	u1, u2, u3 = 1, 0, a
	v1, v2, v3 = 0, 1, b
	while v3 != 0:
		q = u3//v3
		t1, t2, t3 = u1 - q*v1, u2 - q*v2, u3 - q*v3
		u1, u2, u3 = v1, v2, v3
		v1, v2, v3 = t1, t2, t3
	return u1, u2, u3

Fermat(p,x):

• Ý nghĩa: Kiểm tra số p sử dụng định lý Fermat nhỏ với x cơ sở.
• Kiến thức:
  • Định lý Fermat nhỏ: a^(p-1) ≡ 1(mod p) (p: số nguyên tố và a không chia hết cho p)
  • Số giả nguyên tố cơ sở
• Code:

def Fermat(p,x):
	for i in range(x):
		a = sprime[i]
		if MyMath.powMod(a,p-1,p) != 1:
			return False
	return True

Miller_Rabin(p, x):

• Ý nghĩa: Kiểm tra Miller- Rabin với x cơ sở
• Kiến thức: n là số nguyên dương lẻ, n-1 =2^s*m, n trải qua Miller cơ sở b nếu b^t ≡ 1 mod n hoặc b^((2^j)t) ≡ -1 mod n với j nào đó 0 ≤ j ≤ s-1
• Code:

# Q(a,p,m,s) = 1 nếu p trải qua Miller-Rabin cơ sở a
def Q(a, p, m, s):
	x = MyMath.powMod(a,m,p)
	if x == 1:
		return True
	for i in range(0,s+1):
		if x == p - 1:
			return True
		x *= x
		x %= p
	return False

def Miller_Rabin(p, x):
	# x : the number of bases
	# p - 1 = m*2^s (m is odd)
	n = p - 1
	s = 0
	while n & 1 == 0:
		n = n >> 1
		s+= 1
	m = n
	for i in range(x):
		a = sprime[i]
		if Q(a,p,m,s) == False:
			return False
	return True

Tạo khóa

• Lấy 2 số p,q
• Gắn n = p*q, φ(n) = (p-1)(q-1)
• Lấy e sao cho (e, φ(n)) = 1
• Gắn d là nghịch đảo modulo phi của e, xử dụng GCD_extended

def getD(e, phi):
	d = MyMath.GCD_extended(e,phi)[0] #[x,y,z] #d = x
	if d < 0:
		d+= phi
	return d

• In kết quả ra file

Mã hóa

• Lấy khóa công khai (n, e)
• Lấy bản rõ P
• Chuyển các kí tự trong P về số theo bản mã UTF-8 tạo thành mảng các số R
• Ghép các số trong R thành số lớn nhỏ hơn n thành số Pi rồi mã hóa nó thành Ci với công thức: Ci ≡ Pi^e mod n

def encode(n, e, P, file):
	fo = open(file,"w")
	C = ""
	R = convertStringToInt(P, 4)
	A = createBigInt(R, len(str(n)))
	for i in A:
		M = MyMath.powMod(i,e,n)
		M = MyBase.toBase(M,64)
		C+= M + ' '
		fo.write(M+' ')
	fo.close()
	return C

• In mảng số mới ra file với cơ số 64

Giải mã

• Lấy khóa bảo mật (n, d)
• Lấy bản mã C trong file chuyển về cơ số 10
• Lấy từ số trong C là Ci giải mã được Pi với công thức: Pi ≡ Ci^d mod n
• Lấy kết quả tách số rồi chuyển về dạng kí tự
• In kết quả ra file

def decode(n, d, C, base, fileOut): # file PlanintextDecode
	fo = open(fileOut,"w")
	P = ""
	for i in C:
		m = MyMath.powMod(MyBase.toInt(i,64),d,n)
		c = str(m)
		while len(c) % base != 0:
			c = '0' + c
		x = 0
		while x != len(c):
			a = c[x:x+base]
			x+= base
			P+= chr(int(a))
			fo.write(chr(int(a)))
	fo.close()
	return P

Kiến thức

• Tính nghịch đảo modulo bằng giải thuật Euclid mở rộng
• Định lý Euler: a^φ(n) ≡ 1 mod n với (a,n) = 1