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: z ← W mod 2W2^{W}2W và ε ← 0

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} và ε ← 0 nếu w ∈ [0, 2W2^{W}), ngược lại ε ← 1.
  2. Nếu w = x + y + ε’ với x, y ∈ [0, 2W2^{W}) và ε ∈ {0, 1} , thì w = ε 2W2^{W} + 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}

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}

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}

Cho p = 2.147.483.647, W = 8; ta có m = [log⁡2(p)][log_{2}(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}

Cho p = 2.147.483.647, W = 8; ta có m = [log⁡2(p)][log_{2}(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….

Nguồn: viblo.asia

Bài viết liên quan

Thay đổi Package Name của Android Studio dể dàng với plugin APR

Nếu bạn đang gặp khó khăn hoặc bế tắc trong việc thay đổi package name trong And

Lỗi không Update Meta_Value Khi thay thế hình ảnh cũ bằng hình ảnh mới trong WordPress

Mã dưới đây hoạt động tốt có 1 lỗi không update được postmeta ” meta_key=

Bài 1 – React Native DevOps các khái niệm và các cài đặt căn bản

Hướng dẫn setup jenkins agent để bắt đầu build mobile bằng jenkins cho devloper an t

Chuyển đổi từ monolith sang microservices qua ví dụ

1. Why microservices? Microservices là kiến trúc hệ thống phần mềm hướng dịch vụ,