Phương pháp mã hóa liên tiếp và tiêu chuẩn cho tham số e

Bài viết đã phát triển thuật toán giải bài toán RSA thành thuật toán phân tích modulo N của hệ mật RSA hiệu quả trong trường hợp chỉ cần ord hoặc q ord e đủ nhỏ. Với phát triển trên đề xuất bổ sung thêm một tiêu chuẩn cho tham số E cùng với việc tìm các tham số nguyên tố kiểm tra được thỏa mãn tiêu chuẩn đã đưa ra cho hệ mật RSA.
Nội dung trích xuất từ tài liệu:
Phương pháp mã hóa liên tiếp và tiêu chuẩn cho tham số e Nghiên cứu khoa học công nghệ PHƯƠNG PHÁP MÃ HÓA LIÊN TIẾP VÀ TIÊU CHUẨN CHO THAM SỐ E Nguyễn Đào Trường1*, Nguyễn Ngọc Điệp2, Nguyễn Thị Thu Nga3 Tóm tắt: Một tấn công vào hệ mật RSA sử dụng phương pháp “mã hóa liên tiếp” rất có hiệu quả để giải bài toán RSA trong trường hợp các hệ mật RSA với số mũ công khai e có ord  ( N ) e đủ nhỏ. Bài viết đã phát triển thuật toán giải bài toán RSA thành thuật toán phân tích modulo N của hệ mật RSA hiệu quả trong trường hợp chỉ cần ord  ( p ) e hoặc ord  ( q ) e đủ nhỏ. Với phát triển trên đề xuất bổ sung thêm một tiêu chuẩn cho tham số E cùng với việc tìm các tham số nguyên tố kiểm tra được thỏa mãn tiêu chuẩn đã đưa ra cho hệ mật RSA. Từ khóa: Hệ mật RSA, Mã hóa liên tiếp, Tham số, Số mũ công khai. 1. MỘT SỐ KÝ HIỆU, ĐỊNH NGHĨA VÀ KẾT QUẢ Cho S là một tập hữu hạn. Ký hiệu #S là số các phần tử của S. Cho hai số nguyên dương N và e. - Nếu N chia hết cho e, ta nói N là bội của e, còn e là ước của N và ký hiệu là e| N . m - Nếu e | N còn em 1 | N , ta nói e m là ước tuyệt đối của N và ký hiệu là em || N . Cho  N i | i  1,..., k  là k số nguyên dương. Ký hiệu: - gcd  Ni | i  1,..., k : Là số nguyên dương e lớn nhất thỏa mãn e | N i ; i  1,..., k và được gọi là ước chung lớn nhất của  Ni | i  1,..., k  . - lcm  Ni | i  1,..., k : Là số nguyên dương m nhỏ nhất thỏa mãn N i | m; i  1,..., k và được gọi là bội chung nhỏ nhất của  Ni | i  1,..., k . Cho N là một số nguyên dương. Ký hiệu: -  N : Tập các số nguyên 0, 1, ..., N  1 với hai phép toán cộng và nhân rút gọn theo mudulo N. Khi này  N là một vành. - *N : Nhóm nhân của vành  N . Hàm -Euler.  ( N )  #a   N | gcd(a, N )  1 . Ta có:  ( N )  # *N (1.1) Cấp của phần tử trong nhóm - Cho G là một nhóm nhân hữu hạn với đơn vị ký hiệu là 1. Khi đó với mọi phần tử a G luôn tồn tại số tự nhiên d sao cho a  a , ký hiệu là a d , bằng đơn vị. Tức là:  a d ad  1 (1.2) - Giá trị d nhỏ nhất thỏa mãn công thức (1.2) được gọi là cấp của a trong G và được ký hiệu là ord G a . Trong trường hợp G  *N thì ord G a còn được ký hiệu là ord N a . Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 63  Công nghệ thông tin & Khoa học máy tính - (N): Cấp lớn nhất của các phần tử trong nhóm *N . k Công thức tính (N) và (N). Nếu N   pi i với pi là các số nguyên tố khác nhau i 1 thì k  ( N )   ( pi  1) pii 1 (1.3) i 1  ( N )  lcm{( pi  1) pii 1 | i  1,..., k} (1.4) Ngưỡng an toàn tính toán. Ngưỡng an toàn tính toán (thường được xét đến một thời điểm cụ thể) là một con số, ký hiệu là A, sao cho mọi tổ chức, cá nhân đều không thể thực hiện được A phép tính cho đến thời điểm được xét. 2. GIẢI BÀI TOÁN BẰNG PHƯƠNG PHÁP MÃ HÓA LIÊN TIẾP 2.1. Bài toán RSA Cho bản mã C được mã hóa bởi hệ mật RSA với tham số công khai (N, e). Hãy tìm M sao cho M e  C (mod N ) 2.2. Thuật toán mã hóa liên tiếp Tấn công mã hóa liên tiếp [6,7] nhằm tìm bản rõ M từ bản mã C theo hệ mật RSA với bộ tham số công khai (N, e) được thực hiện theo thuật toán sau đây. Thuật toán 1. (mã hóa liên tiếp giải bài toán RSA) Input: C, (N, e) Ouput: M thỏa mãn M e  C (mod N ) Begin 1. M  C 2. X  M e (mod N ) 3. while (X  C) do 3.1 M  X 3.2 X  M e (mod N ) End 4. return M 2.3. Phân tích thuật toán Trước hết chúng ta thấy rằng nếu thuật toán dừng tức là X = C thì với X được tính theo bước 2 hoặc bước 3.2 ta có ngay C  X  M e (mod N ) . Đẳng thức trên có nghĩa là đầu ra của thuật toán đúng là bản rõ cần tìm. Việc còn lại của chúng ta ở đây là chứng tỏ thuật toán 1 luôn dừng và xác định độ phức tạp tính toán của nó. Kết quả 1. Thuật toán 1 sẽ dừng sau đúng ord  ( N ) e  1 vòng lặp ở bước 3. Chứng minh: Với M xuất phát từ bước 1 chính là C nên X thu được tại bước 2, ký hiệu là X 0 chính là X 0  C e (mod N ) (2.1) 64 N. Đ. Trường, N.N. Điệp,. ..“Phương pháp mã hóa liên tiếp… cho tham số e.” Nghiên cứu khoa học công nghệ Ký hiệu giá trị X tính được tại vòng lặp thứ t (t  1) ở bước 3 là X t , theo bước 3.2 ta có X t  M e (mod N ) và theo bước 3.1 thì M  X t 1 vậy ta có X t  X te1 (mod N ) (2.2) Từ (2.1) và (2.2) ta thu được t 1 X t  X e (mod N ) (2.3) Với t  ord  ( N ) e  1 thì (2.3) trở thành ord ( N )e Xt  Ce (mod N ) ...