Một số thuật toán cơ bản được ứng dụng trong an toàn thông tin (Phần 2)

Phần 1: https://viblo.asia/p/mot-so-thuat-toan-co-ban-duoc-ung-dung-trong-an-toan-thong-tin-phan-1-Ljy5VvRk5ra

a. Thuật toán cộng chính xác bội

• Thuật toán cộng và trừ trên trường hữu hạn được đưa ra dưới dạng các thuật toán tương ứng cho các số nguyên w. Phép gán dạng “(ɛ, z) ← w” được định nghĩa như sau:

1. z ← W mod 2W2^{W}2W và ε ← 0 nếu w ∈ [0, 2W2^{W}2W), ngược lại ε ← 1.
2. Nếu w = x + y + ε’ với x, y ∈ [0, 2W2^{W}2W) và ε ∈ {0, 1} , thì w = ε 2W2^{W}2W + z và ε được gọi là “bit nhớ” (carry bit) cho phép cộng mỗi một từ đơn (ε = 1 nếu và chỉ nếu z < x + ε’ )

VD: Cho a = (0, 11, 173, 248); b = (0, 1, 226, 64), với w = 8, t = 4. Tìm c = a + b mod 2Wt2^{Wt}2Wt

a =[0,11,173,248]
b =[0,1,226,64]
W =8
t =4defsolve(a, b, W, t):
	a.reverse()
	b.reverse()
	c =[]
	epsilon =0
	e =pow(2,8)for i inrange(t):
		s = a[i]+ b[i]+ epsilon
		x = s%e
		if(s > e): epsilon =1else: epsilon =0 
		c.append(x)return[epsilon, c[::-1]]if __name__ =='__main__':print(solve(a, b, W, t))

b. Thuật toán trừ chính xác bội

VD: Cho a = (0, 11, 173, 248); b = (0, 1, 226, 64), với w = 8, t = 4. tìm c = a – b mod 2Wt2^{Wt}2Wt

a =[0,11,173,248]
b =[0,1,226,64]
W =8
t =4defsolve(a, b, W, t):
	a.reverse()
	b.reverse()
	c =[]
	epsilon =0
	e =pow(2,8)for i inrange(t):
		d = a[i]- b[i]- epsilon
		if(d <0): 
			d += e
			epsilon =1else: epsilon =0
		x = d%e
		c.append(x)return epsilon, c[::-1]if __name__ =='__main__':print(solve(a, b, W, t))

c. Thuật toán cộng trên FpF_{p}Fp​

Cho p = 2.147.483.647, W = 8; ta có m = [log⁡2(p)][log_{2}(p)][log2​(p)] = 31; t = [m/W] = 4. a = (0, 11, 173, 248); b = (0, 1, 226, 64). 3 Tìm c = a + b mod p

import math, re

p =2147483647
a =[157,0,173,23]
b =[169,1,0,64]
W =8
m =round(math.log2(p))
t =round(m/W)defint_to_dec(n):
	n =bin(n)[2:].zfill(8*t)
	b = re.findall('d{8}', n)
	c =['0b'+ i for i in b]return[int(i,2)for i in c]defdec_to_int(n):
	n =''.join([bin(i)[2:].zfill(8)for i in n])returnint(n,2)defmultiprecision_addition(a, b, W, t):
	a.reverse()
	b.reverse()
	c =[]
	epsilon =0
	e =pow(2,8)for i inrange(t):
		s = a[i]+ b[i]+ epsilon
		x = s%e
		if(s > e): epsilon =1else: epsilon =0 
		c.append(x)return[epsilon, c[::-1]]defmultiprecision_subtraction(a, b, W, t):
	a.reverse()
	b.reverse()
	c =[]
	epsilon =0
	e =pow(2,8)for i inrange(t):
		d = a[i]- b[i]- epsilon
		if(d <0): 
			d += e
			epsilon =1else: epsilon =0
		x = d%e
		c.append(x)return epsilon, c[::-1]if __name__ =='__main__':[epsilon, c]= multiprecision_addition(a, b, W, t)
	p = int_to_dec(p)if epsilon ==1:
		d = multiprecision_subtraction(c, p, W, t)elif epsilon ==0:
		d = multiprecision_subtraction(p, c, W, t)print(d)

d. Thuật toán trừ trên FpF_{p}Fp​

Cho p = 2.147.483.647, W = 8; ta có m = [log⁡2(p)][log_{2}(p)][log2​(p)] = 31; t = [m/W] = 4. a = (0, 11, 173, 248); b = (0, 1, 226, 64). 3 Tìm c = a – b mod p

import math, re

p =2147483647
a =[0,11,173,248]
b =[0,1,226,64]
W =8
m =round(math.log2(p))
t =round(m/W)defint_to_dec(n):
	n =bin(n)[2:].zfill(8*t)
	b = re.findall('d{8}', n)
	c =['0b'+ i for i in b]return[int(i,2)for i in c]defdec_to_int(n):
	n =''.join([bin(i)[2:].zfill(8)for i in n])returnint(n,2)defmultiprecision_addition(a, b, W, t):
	a.reverse()
	b.reverse()
	c =[]
	epsilon =0
	e =pow(2,8)for i inrange(t):
		s = a[i]+ b[i]+ epsilon
		x = s%e
		if(s > e): epsilon =1else: epsilon =0 
		c.append(x)return[epsilon, c[::-1]]defmultiprecision_subtraction(a, b, W, t):
	a.reverse()
	b.reverse()
	c =[]
	epsilon =0
	e =pow(2,8)for i inrange(t):
		d = a[i]- b[i]- epsilon
		if(d <0): 
			d += e
			epsilon =1else: epsilon =0
		x = d%e
		c.append(x)return epsilon, c[::-1]if __name__ =='__main__':[epsilon, c]= multiprecision_subtraction(a, b, W, t)
	p = int_to_dec(p)if epsilon ==1:
		d = multiprecision_addition(c, p, W, t)elif epsilon ==0:
		d = c
	print(d)

Còn tiếp….