Bài tập lớn - Số học thuật toán

Mã hóa RSA

1. Giới thiệu chung

• Tác giả:
  • Sinh viên: Nguyễn Tú Anh
  • MSV: A29888
  • Trường: Đại học Thăng Long
• Môn học và đề tài:
  • 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)

2. Giới thiệu chung cấu trúc bài tâp lớn

• 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

3. MyMath - Hàm toán học

• powMod(a, b, m)

  • Ý 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

• GCD(a, b)
  • Ý 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)

• GCD_extended(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

4. PrimeTest - Các hàm kiểm tra tính nguyên tố

• 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

5. Mã hóa RSA

• 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