An toàn của hệ thống mã hoá- P3

An toàn của hệ thống mã hoá- P3:Shannon định nghĩa rất rõ ràng, tỉ mỉ các mô hình toán học, điều đó có nghĩalà hệ thống mã hoá là an toàn. Mục đích của người phân tích là phát hiện rakhoá k, bản rõ p, hoặc cả hai thứ đó. Hơn nữa họ có thể hài lòng với một vàithông tin có khả năng về bản rõ p nếu đó là âm thanh số, nếu nó là văn bảntiếng Đức, nếu nó là bảng tính dữ liệu,...
Nội dung trích xuất từ tài liệu:
An toàn của hệ thống mã hoá- P3 Upload by Share-Book.com L(a,p) = 0 nếu a chia hết cho p. L(a,p) = 1 nếu a là thặng dư bậc 2 mod p. L(a,p) = -1 nếu a không thặng dư mod p.Một phương pháp dễ dàng để tính toán ra L(a,p) là : L(a,p) = a (p-1)/2 mod p3.6 Ký hiệu Jacobi (Jacobi Symboy)Ký hiệu Jacobi được viết J(a,n), nó là sự khái quát hoá của ký hiệu Lagrăng,nó định nghĩa cho bất kỳ cặp số nguyên a và n. Ký hiệu Jacobi là một chứcnăng trên ập hợp số thặn g dư thấp của ước số n v à có th tính toán theo t ểcông thức sau: Nếu n là số nguyên tố, thì J(a,n) = 1 với điều kiện a là thặng dư bậc hai modulo n . Nếu n là số nguyên tố, thì J(a,n) = -1 với điều kiện a không là thặng dư bậc hai modulo n . Nếu n không phải là số nguyên tố thì Jacobi J(a,n)=J(h,p1) × J(h,p2) ×. . . × J(h,pm) với p1,p2. . .,pm là các thừa số lớn nhất của n.Thuật toán này tính ra số Jacobi tuần hoàn theo công thức sau : 1. J(1,k) = 1 2. J(a×b,k) = J(a,k) × J(b,k) 3. J(2,k) =1 Nếu (k2-1)/8 là chia hết J(2,k) =-1 trong các trường hợp khác. 4. J(b,a) = J((b mod a),a) 5. Nếu GCD(a,b)=1 : a. J(a,b) × J(b,a) = 1 nếu (a-1)(b-1)/4 là chia hết. b. J(a,b) × J(b,a) = -1 nếu (a-1)(b-1)/4 là còn dư. Trang 16 Upload by Share-Book.comSau đây là thuật toán trong ngôn ngữ C :int jacobi(int a,int b){ int a1,a2; if(a>=b) a%=b; if(a==0) return 0; if(a==1) return 1; if(a==2) if(((b*b-1)/8)%2==0) return 1; else return -1; if(a&b&1) (cả a và b đều là số dư) if(((a-1)*(b-1)/4)%2==0) return +jacobi(b,a); else return -jacobi(b,a); if(gcd(a,b)==1) if(((a-1)*(b-1)/4)%2==0) return +jacobi(b,a); else return -jacobi(b,a); factor2(a,&a1,&a2); return jacobi(a1,b) * jacobi(a2,b);}Nếu p là số nguyên tố có cách tốt hơn để tính số Jacobi như dưới đây : 1. Nếu a=1 thì J(a/p)=1 2. Nếu a là số chai hết, thì J(a,p)=J(a/2,p) × (-1)(p^2 –1)/8 3. Nếu a là số dư khác 1 thì J(a,p)=J(p mod a, a) × (-1)(a-1)×(p-1)/4 Trang 17 Upload by Share-Book.com3.7 Định lý phần dư trung hoa.Nếu bạn biết cách tìm thừa số nguyên tố của một số n, thì bạn có thể đã sửdụng, một số điều gọi là định lý phần dư trung hoa để giải quyết trong suốthệ phương trình. Bản dịch cơ bản của đinh lý này được khám phá bởi toánhọc Trung Hoa vào thế kỷ thứ nhất.Giả sử, sự phân tích thừa số của n=p1×p2×. . .×pt thì hệ phương trình (X mod pi) = ai , với i=1,2,. . .tcó duy nhất một cách giải, tại đó x nhỏ hơn n.Bởi vậy, với a,b tuỳ ý sao cho a < p và b < q (p,q là số nguyên tố) thì tồn tạiduy nhất a,x ,khi x nhỏ hơn p×q thì x ≡ a (mod p), và x ≡ b (mod q)Để tìm ra x đầu tiên sử dụng thuật toán Euclid để tìm u, ví dụ : u × q ≡ 1 (mod p)Khi đó cần tính toán : x=((( a-b)×u) mod p ) × q + bDưới đây là đoạn mã định lý phần dư trung hoa trong ngôn ngữ C :Int chinese remainder(size t r, int *m, int *u){ size t i; int modulus; int n; modulus = 1; for ( i=0; i Upload by Share-Book.com n%=modulus; } return n;}3.8 Định lý Fermat.Nếu m là số nguyên tố, và a không phải là bội số của m thì định lý Fermatphát biểu : am-1 ≡ 1(mod m)4. Các phép kiểm tra số nguyên tố.Hàm một phía là một khái niệm cơ bản của mã hoá công khai, việc nhân haisố nguyên tố được phỏng đoán như là hàm một phía, nó rất dễ dàng nhân cácsố để tạo ra một số lớn, nhưng rất khó khăn để phân tích số lớn đó ra thànhcác thừa số là hai số nguyên tố lớn.Thuật toán mã hoá công khai cần thiết tới những số nguyên tố. Bất kỳ mạngkích thước thế nào cũng cần một số lượng lớn số nguyên tố. Có một vàiphương pháp để sinh ra số nguyên tố. Tuy nhiên có một số vấn đề được đặtra đối với số nguyên tố như sau : Nếu mọi người cần đến những số nguyên tố khác nhau, chúng ta sẽ không đạt được điều đó đúng không. Không đúng, bởi vì trong thực tế có tới 10150 số nguyên tố có độ dài 512 bits hoặc nhỏ hơn. Điều gì sẽ xảy ra nếu có hai người ngẫu nhiên chọn cùng một số nguyên tố?. Với sự chọn lựa từ số lượng 10150 số nguyên tố, điều kỳ quặc này xảy ra là xác xuất nhỏ hơn so với sự tự bốc cháy của máy tính. Vậy nó không có gì là đáng lo ngại cho bạn hết.4.1 Soloway-StrassenSoloway và Strasse ...