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

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 63 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ó ( )Nord 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 ( )pord e hoặc ( )qord 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 . - Nếu |me N còn 1 |me N  , ta nói me là ước tuyệt đối của N và ký hiệu là ||me N . Cho  | 1,...,iN i k là k số nguyên dương. Ký hiệu: -   gcd | 1,...,iN i k : Là số nguyên dương e lớn nhất thỏa mãn | ; 1,...,ie N i k  và được gọi là ước chung lớn nhất của  | 1,...,iN i k . -   | 1,...,ilcm N i k : Là số nguyên dương m nhỏ nhất thỏa mãn | ; 1,...,iN m i k  và được gọi là bội chung nhỏ nhất của  | 1,...,iN i k . Cho N là một số nguyên dương. Ký hiệu: - N : Tập các số nguyên  0, 1, ..., 1N  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.  ( ) # | gcd( , ) 1NN a a N    . Ta có: *( ) # NN   (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 d a a a    , ký hiệu là da , bằng đơn vị. Tức là: 1da  (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à Gord a . Trong trường hợp * NG   thì Gord a còn được ký hiệu là Nord a . Công nghệ thông tin & Khoa học máy tính N. Đ. Trường, N.N. Điệp,. ..“Phương pháp mã hóa liên tiếp cho tham số e.” 64 - (N): Cấp lớn nhất của các phần tử trong nhóm * N . Công thức tính (N) và (N). Nếu 1 i k i i N p   với pi là các số nguyên tố khác nhau thì 1 1 ( ) ( 1) i k i i i N p p     (1.3) 1( ) {( 1) | 1,..., }ii iN lcm p p i 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 (mod )eM C 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 (mod )eM C N Begin 1. M  C 2. (mod )eX M N 3. while (X  C) do 3.1 M  X 3.2 (mod )eX M 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 (mod )eC X M 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 ( ) 1Nord e  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à 0X chính là 0 (mod ) eX C N (2.1) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 65 Ký hiệu giá trị X tính được tại vòng lặp thứ t (t  1) ở bước 3 là tX , theo bước 3.2 ta có (mod )etX M N và theo bước 3.1 thì 1tM X  vậy ta có 1 (mod )t e tX X N (2.2) Từ (2.1) và (2.2) ta thu được 1 (mod ) te tX X N   (2.3) Với ( ) 1Nt ord e  thì (2.3) trở thành ( ) (mod ) ord eNe tX C N   (2.4) Biết rằng với mọi giá trị *Na và với mọi số nguyên dương m ta có: mod ( ) (mod )m m Na a N (2.5) theo định nghĩa về cấp thì ( ) 1(mod ( ))N ord e e N  nên thay (2.5) với ( )N ord e m e  vào (2.4) thì vế phải của nó chính là C vậy Kết quả 1 đã được chứng minh. Từ kết quả trên ta có: Hệ quả 1. Chi phí tính toán của thuật toán 1 là ( )Nord e phép lũy thừa với số mũ e trong N . Như vậy nếu e có ( )Nord e đủ nhỏ thì theo hệ quả 1, người tấn công sẽ luôn giải được bài toán RSA và khi này hệ mật RSA sẽ không an toàn. 3. PHÂN TÍCH MODULE N CỦA HỆ MẬT RSA BẰNG PHƯƠNG PHÁP MÃ HÓA LIÊN TIẾP 3.1. Thuật toán Việc phân tích modulo N của hệ mật RSA với bộ tham số công khai (N, e) theo phương pháp mã hóa liên tiếp [6] được thực hiện theo thuật toán sau: Thuật toán 2 (mã hóa liên tiếp phân tích modulo N) Input: (N, e) là bộ tham số khóa công khai RSA Ouput: p là ước nguyên tố của N Begin 1. X  random(1, N); Y  X 2. p  gcd(X, N) 3. while (p  {1, N}) do 3.1. modeX X N 3.2. p  gcd(X  Y, N) End 4. return p 3.2. Phân tích thuật toán 2 Kết quả 2. Giả sử N = pq và nếu các điều kiện sau đây được thỏa mãn: ( ) ( )p q ord e ord e  (3.1) Giá trị Y lấy trong bước 1 thỏa mãn ( )(mod ) v (mod ( ))p ord euY Y q u e q  íi (3.2) Công nghệ thông tin & Khoa học máy tính N. Đ. Trường, N.N. Điệp,. ..“Phương pháp mã hóa liên tiếp cho tham số e.” 66 thì thuật toán 2 sẽ dừng với đầu ra là ước nguyên tố p của N. Chứng minh: Không giảm tính tổng quát, giả sử ( ) (q)pord e ord e  , giống như lập luận đã sử dụng để chứng minh Kết quả 1 ta có giá trị X tính được ở vòng lặp thứ t, ký hiệu là Xt, của bước 3 chính là (mod ) teX N với X là giá trị được lấy trong bước 1 và do đó ta có (mod ) te tX Y N (3.3) Xét phần dư theo phép chia cho p cả hai vế của (3.3) ta được mod ( (mod )) mod mod t te e tX p Y N p Y p  (3.4) Với ( )pt ord e ta có 1(mod ( )) te p và vì vậy vế phải của (3.4) chính là modY p hay (mod )tX Y p (3.5) Tương tự, xét phần dư theo phép chia cho q cả hai vế của (3.3) ta được mod ( (mod )) mod mod t te e tX p Y N p Y q  (3.6) Từ giả thiết ( ) (q)pord e ord e  nên giá trị ( ) 1(mod ( ))p ord etu e e q    đồng thời với giả thiết (3.2) ta có (mod )tX Y q (3.7) Từ (3.5) và (3.7) cho thấy tX Y là bội của p nhưng không là bội của q và điều này dẫn đến  gcd( , ) 1,tX Y N p N   cho nên thuật toán dừng và đầu ra chính là ước nguyên tố của N. Tóm lại Kết quả 2 đã được chứng minh. Giống như Kết quả 1 ta có hệ quả sau: Hệ quả 2. Chi phí tính toán của thuật toán 2 là  ( ) ( )min ,p qm ord e ord e  phép lũy thừa với số mũ e và m phép tìm ước chung lớn nhất của hai số nguyên trong N . 4. TIÊU CHUẨN CHO THAM SỐ E 4.1 Tiêu chuẩn Để chống được tấn công thám mã được đưa ra trong thuật toán 1 ta cần đến điều kiện về tham số e là ( )Nord e A  , với A là ngưỡng an toàn tính toán (4.1) Bởi vì khi này theo hệ quả 1, chi phí để thực hiện thuật toán 1 là vượt quá khả năng của người tấn công. Để chống được tấn công phân tích số N được đưa ra trong thuật toán 2 chúng ta có thể đưa ra đề xuất về tham số e đó là thỏa mãn ít nhất một trong hai điều kiện sau: ( ) ( )p qord e ord e  (4.2) Hoặc Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 67 ( ) ( ) p q ord e A ord e A      (4.3) Hiển nhiên (4.2) là điều kiện không thành công của thuật toán 2, còn (4.3) làm cho chi phí để thực hiện thành công thuật toán 2 là vượt quá khả năng của kẻ tấn công. Rõ ràng nếu thỏa mãn điều kiện (4.3) thì (4.1) cũng được thỏa mãn, do đó việc thỏa mãn (4.3) là đủ để chống lại cả hai tấn công đã trình bày. Cho nên tiêu chuẩn cho tham số e được đưa ra ở đây là. Tiêu chuẩn. e thỏa mãn điều kiện (4.3). 4.2 Kiểm tra sự thỏa mãn tiêu chuẩn của tham số E Biết rằng trong tất cả các tiêu chuẩn cho bộ tham số của hệ mật RSA đã được ban hành trên thế giới chẳng hạn [1, 2, 3, 4] thì việc sinh các tham số luôn được bắt đầu từ chọn e sau đó rồi mới đến tìm các tham số nguyên tố p và q sao cho bộ tham số 1( ; ; mod ( ))N pq e d e N  thỏa mãn toàn bộ các tiêu chuẩn. Bây giờ muốn kiểm tra điều kiện (4.3) cho tham số e ta cần tính được hay ít ra cũng phải ước lượng được hai giá trị ( )pord e và ( )qord e . Do ( )pord e là ước của ( ( ))p  và ( )qord e là ước của ( ( ))q  nên việc ước lượng hai giá trị nói trên có thể được thực hiện bởi kết quả hiển nhiên sau đây. Bổ đề 1. Cho N là một số nguyên dương, r là ước nguyên tố của ( ( ))N  . Khi đó nếu m od ( ) 1 v i ( ( )) /de N d N r   í (4.4) thì ( )Nord e là bội của mr với || ( ( ))mr N  . Như vậy, nếu giá trị r nêu trong Bổ đề 1 thỏa mãn r A thì ta có ngay ( )Nord e A  cho nên bằng cách chỉ ra được các số nguyên tố pr và qr không nhỏ hơn A tương ứng là ước của ( ( ))p  và ( ( ))q  thì việc kiểm tra sự thỏa mãn Tiêu chuẩn 1 được thực hiện dễ dàng thông qua sự thỏa mãn điều kiện (4.4) với N lần lượt thay bằng p và q. Khi đó cặp  A,p qr r A  sẽ là bằng chứng thỏa mãn tiêu chuẩn. 4.3. Tìm số nguyên tố thỏa mãn tiêu chuẩn cho E Hiển nhiên các số nguyên tố p có đủ bằng chứng thỏa mãn tiêu chuẩn với tham số e phải thỏa mãn hai điều kiện sau: Thứ nhất: ( ( ))p  có ước nguyên tố r A (4.5) Thứ hai: ( ( ))/ mod ( ) 1p re p    (4.6) Từ đó bằng việc sinh ngẫu nhiên một số nguyên tố r A rồi tìm ngẫu nhiên một số nguyên tố 1p trong tập { 1 1|p rx x  nguyên dương} thì các số nguyên tố p trong tập { 1 1|p p x x  nguyên dương} sẽ thỏa mãn | ( ( ))r p  . Nói một cách khác là điều Công nghệ thông tin & Khoa học máy tính N. Đ. Trường, N.N. Điệp,. ..“Phương pháp mã hóa liên tiếp cho tham số e.” 68 kiện (4.5) đã được thỏa mãn. Bằng kiểm tra thêm điều kiện (4.6) để có được số nguyên tố cần tìm. TÀI LIỆU THAM KHẢO [1]. TCVN 7635:2007, Tiêu chuẩn Quốc gia. Kỹ thuật Mật mã - Chữ ký số. Hà nội 2007. [2]. ANSI X9.31, American National Standard for Financial Services X9.31, “Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA)”,2-1998. [3]. FIPS PUB 186-3, “Digital Signature Standard (DSS)”, June, 2009. [4]. FIPS PUB 186-4, “Digital Signature Standard (DSS)”, July, 2013. [5]. Richard Crandall, Carl Pomerance (2005), “Prime Numbers, A Computational Perspective”, Second Edition, Springer Science + Business Media, In. [6]. M. Jason Hinek, “Cryptanalysis of RSA and its Variants”, Chapman Hall, 2010. [7]. J. Friedlander, Carl Pomerance, and I. Shparlinski, “Period of the power generator and small values of Carmichael’s function”, Math. Comput., 70(236):1591–1605, 2001. ABSTRACT THE CONTINUOUS ENCRYPTION METHOD AND PARAMETER E CRITERION An attack on RSA cryptosystem using the method of “continuous encryption” very effective to solve the problem in the case of the RSA cryptosystem with public exponent ( )Nord e small enough. This article developes the algorithm which solve RSA problem become the algorithm to analysis modulo N of RSA effectively in case the public exponent ( )pord e or ( )qord e small enough. With above development, we add a criterion for parameter E and the search examable prime parameters correspond to standards issued for RSA cryptosystem. Keywords: RSA cryptosystem, Continuous encryption, Parameter, Public exponent. Nhận bài ngày 12 tháng 06 năm 2015 Hoàn thiện ngày 30 tháng 06 năm 2015 Chấp nhận đăng ngày 22 tháng 10 năm 2015 Địa chỉ: 1 Học viện Kỹ thuật mật mã, Ban Cơ yếu Chính phủ; 2 Viện Khoa học - Công nghệ mật mã, Ban Cơ yếu Chính phủ ; 3 Sở Giáo dục - Đào tạo Bắc Ninh, Bắc Ninh. * Email: truongnguyendao@gmail.com