Tài liệu Các tính chất đại số của hệ mã rsa và khả năng mở rộng (tóm tắt)

1. P 2. GS. N ĐẠI HỌC QUỐC GIA TP. HCM Tp. Hồ Chí Minh, 2015 TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Công trình được hoàn thành tại: TRẦN ĐÌNH LONG CÁC TÍNH CHẤT ĐẠI SỐ CỦA HỆ MÃ CÔNG KHAI RSA VÀ KHẢ NĂNG MỞ RỘNG TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TP. HỐ CHÍ MINH Người hướng dẫn khoa học 1. PGS. TS. TRẦN ĐAN THƯ 2. PGS. TS. NGUYỄN ĐÌNH THÚC Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 62 48 01 01 Phản biện 1: Phản biện 2: Phản biện 3: Phản biện độc lập 1: TÓM TẮT LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Phản biện độc lập 2: Luận án sẽ được bảo vệ trước Hội đồng chấm luận án họp tại N gướng dẫn khoa học vào lúc giờ ngày tháng năm Field Sieve) với đô ô phức tạp là Có thể tìm hiểu luận án tại thư viện: - Thư viện Khoa học Tổng hợp Tp.HCM - Thư viện Trường Đại học Khoa học Tự Nhiên đó m là số bit của RSA là mô ôt hê ô mã hóa nổi tiếng do 3 tác giả Rivest, Shamir và Adleman giới thiệu vào năm 1978 [5]. Viê ôc không có mô ôt hê ô mã nào dùng rô ông rãi như RSA cho đến bây giờ cho thấy đây là mô ôt hê ô mã an toàn, khó bị tấn công. Chính vì vâ yô có rất nhiều công trình liên quan đến RSA. Trên thế giới, có thể chia các công trình lý thuyết liên quan đến RSA làm hai loại: phát triển các biến thể của RSA và thám mã RSA. Sự phát triển các biến thể của RSA có thể chia làm hai hướng. Trong hướng thứ nhất, các tác giả tập trung vào hệ mã RSA gốc nhưng cải tiến các thuật toán mã hóa và giải mã nhằm giảm độ phức tạp tính toán hoặc xây dựng RSA trên vành Zn với n có dạng phức tạp hơn thay vì là tích của hai số nguyên tố phân biệt. Trong hướng thứ hai, các biến thể của RSA được xây dựng trên các cấu trúc đại số phức tạp hơn. Các công trình của Varadharajan V. và Odoni (1985), N. Demytko (1993), El-Kassar A.N., R. Hatary và Y. Awad (2004) là các ví dụ cho hướng nghiên cứu này. Song song với viê ôc phát triển các biến thể của RSA, bài toán thám mã RSA cũng thu hút được nhiều tác giả . Cách tấn công cổ điển dựa vào bài toán phân tích mô ôt số nguyên dương n thành các thừa số nguyên tố, hiê ôn nay thuâ ôt toán phân tích hiệu quả nhất là thuâ ôt toán Sieve (General Number 1 3 2 log 3 m  với c  2 , trong n . Hiê ôn nay có rất nhiều cách tấn công vào RSA với các công cụ khác nhau. Năm 1990, M. Wiener đưa ra cách tấn công RSA trong trường hợp khóa riêng MỞ ĐẦU e   c  O 1   m 1 d n4 bằng công cụ liên phân số. D. Boneh và G. Durfee (1999) đạt được kết quả tốt hơn với d n 0.292 , bằng cách giải bài toán tìm phần tử gần đúng có nghịch đảo nhỏ. Sau lần giới thiệu đầu tiên của D. Coppersmith tại Eurocrypt 1996, các thuâ ôt toán tìm cơ sở thu gọn của dàn là mô tô công cụ rất hiê uô quả để tấn công RSA. Trong nước, các công trình hay luâ ôn án liên quan đến RSA còn rất khiêm tốn. Các luâ ôn án thường chỉ dừng lại ở mức hiện thực RSA có cải tiến các thuâ ôt toán số học trong mã hóa và giải mã; khảo sát áp dụng chữ ký điê ôn tử của RSA; liê ôt kê lại các phương pháp tấn công RSA hay áp dụng RSA. Xuất phát từ những khảo sát trên đây về hê ô mã RSA ở trong nước và quốc tế, luâ ôn án này nhằm giải quyết các vấn đề sau: (1) Nghiên cứu hê ê mã RSA nguyên gốc và tất cả các biến thể của nó. Giải thích vì sao các biến thể của RSA chỉ xây dựng trên các cấu trúc đại số khác với Z n , trong đó n là tích của các số nguyên tố phân biê êt. (2) Căn cứ vào nghiên cứu trên, đề xuất sơ đồ tổng quát cho RSA. (3) Căn cứ vào sơ đồ,, xây dựng một biến thể mới cho RSA. (4) Tìm hiểu các kỹ thuâ êt tấn công đã biết vào RSA, qua đó cải tiến mô êt số kỹ thuâ êt và giải quyết mô êt số bài toán còn mở trong thám mã RSA. Nô ôi dung của luâ ôn án gồm các phần sau. Phần mở đầu giới thiệu tổng quan về các nghiên cứu RSA trong và ngoài nước, đồng thời nêu ra các vấn đề cần giải quyết cho luận án. Zn và một số kết quả về thám mã RSA. Chương 2 đề câ ôp đến các kết quả của tác giả về việc xây dựng sơ đồ cho RSA và một biến thể của RSA được xây dựng dựa trên sơ dồ này. Chương 3 đề câ ôp đến các kết quả của tác giả trong lĩnh vực thám mã RSA bao gồm việc đưa ra diều kiện nhằm đảm bảo phương pháp tấn công RSA bằng dàn hai chiều luôn thành công và việc đưa bài toán DLP GL 2, p về bài toán DLP trên trường cơ sở. trên nhóm nhân được giải mã thành c d med m mod n . 1.1.2 Nhâ ên xét về hê ê mã Chương 1 mô tả chi tiết hơn về hệ mã RSA gốc, các biến thể của RSA trên các cấu trúc khác với Giải mã - c Nếu n p1r p2 r … p k r p 1 , p 2 , … , pk 1 2 là các là mô ôt số nguyên dương, trong đó k số nguyên việc trình bày, các kiến thức cơ sở về dàn sẽ được nhắc lại trong phụ lục. Phần kết luâ ôn tóm tắt lại những kết quả mà luận án đã đạt được, đồng thời nêu ra mô ôt số hướng nghiên cứu mở có thể phát triển được. phân biê ôt và  r i ∈ Z , r i 0 i1,2,… , k  , ta sẽ kí hiê ôu rad  n  p1 p 2 … p k . T. Zn Collins et. al. vào 1997 đã xây dựng hệ mã RSA trên n rad  n . Chúng tôi sẽ chỉ ra rằng nhất của n rad  n F : Z n → Z n mà  F  x x k k ≠1 là đơn ánh. Khi đó khi là dạng duy Zn . n nếu chúng ta có thể xây dựng RSA trên Mê ênh đề 1.1 Giả sử tồn tại số tự nhiên Do các thuật toán tìm cơ sở thu gọn trên dàn được dùng nhiều trong tố sao cho ánh xạ n rad  n . 1.2 RSA trên vành Z n Các công trình khảo sát RSA trên vành cơ sở Zn tập trung vào hai hướng. Trong hướng thứ nhất, các tác giả tập trung vào hệ mã RSA gốc CHƯƠNG 1: TỔNG QUAN VỀ RSA nhưng cải tiến các thuật toán mã hóa, giải mã nhằm giảm độ phức tạp tính 1.1 Hê ê mã hóa RSA gốc toán hoặc thêm vào các kỹ thuật khi mã hóa nhằm nâng cao độ an toàn của 1.1.1 Mô tả hê ê mã hệ mã. Có thể kể ra các kỹ thuật cải tiến cho RSA gốc như tạo ra văn bản mã Sinh khóa-Choôn hai số nguyên tố phân biê ôt p , q -Choôn  số  nguyên φ  n   p−1 q−1 . -Tính  e , φ  n 1 mà hóa ngẫu nhiên, tạo đồng thời nhiều chữ ký điện tửhay thêm vào các thuật với  c me  mod n . bản m ∈Z n Zn n với không còn là tích của hai số nguyên tố phân biệt. Hai kết quả đáng kể trong hướng n , e như khóa công khai và giữ d văn toán nhằm thực hiện nhanh quá trình mã hóa và giải mã. Trong hướng thứ hai, các tác giả khảo sát các hệ mã RSA trên vành d e  mod φ  n  . -Công bố Mã hóa -Môôt −1 e n pq . và tính sẽ được làm khóa riêng. mã hóa thành này thuộc về T. Collins khảo sát trường hợp n là tích của nhiều số nguyên tố phân biệt (MultiPrime RSA), và T. Takagi k n p q trong đó p ,q khảo sát khi n có dạng là hai số nguyên tố phân biệt, còn k là số nguyên dương (MultiPower RSA). Các biến thể này của RSA sau đó được các tác giả khác kết hợp với các kỹ thuật cải tiến trong hướng thứ nhất. 1.3 Các biến thể của RSA trên các cấu trúc khác Zn 1.3.1 RSA trên vành các ma trâ ên (Varadharajan V. và Odoni [6], 1985) p , q là hai số nguyên tố, Giả sử  M l  p , M l  q và hiê ôu vuông cấp l×l n pq M l n không suy biến hê ô số tương ứng trên       p − p … p − p   q −1  q −q …  q −q l l N p  p −1 l l l l−1 l −1 l l∈N   Z p, Zq nguyên e ,d . Kí và , Chọn hai thỏa   1 e , d  N n , e , N n 1 mãn và n M l n . Từ đó phép chúng ta mã hóa In trong đó m ∈ M l n . Điều này cho med m với mọi m d c ≡ m cho các văn bản thành là ma trâ ôn đơn vị trong c≡m e và giải mã bằng cách tính m ∈ M l n . 1.3.2 RSA trên nhóm đường cong elliptic (N. Demytko [4], 1993) Giả sử rằng p 3 nguyên được chọn sao cho cong elliptic theo modulo là mô ôt số nguyên tố và 3 a ,b là các số 2 4 a  27 b ≠ 0 mod p . Nhóm đường p , được kí hiê ôu là đường cong elliptic bù với nhóm E p a , b  E p a , b  . Nhóm được kí hiê uô là 3 y  x  ax  b kí hiê ôu là ∞ ; nhưng tọa đô ô u , v ∈Z p v và Z p , cùng với mô ôt phần tử cũng trên y y u √ v có dạng không phải là mô ôt bình phương trong E p a , b  . Bâ ôc của các nhóm trên thỏa mãn với Z p . Phép  E p a , b  được định nghĩa hoàn toàn tương tự như phép + toán + trên được kí hiê ôu tương ứng là E p a , b    Epa ,b ∨ và và  Ep a,b ∨ , các số này có thể tính được bằng các thuâ ôt toán thời gian   đa thức. Chọn hai số nguyên tố phân biê ôt ed ≡ 1 mod N n  . Định lý Lagrange trong lý thuyết nhóm suy ra rằng m N  I n ∈m ∈ M l n 2 phương trình  E p a , b  , N n N p . N q. số  là các nhóm nhân các ma trâ ôn Z n . Bâ ôc của các nhóm này là Nq và  E p a , b  , đó là tâ ôp hợp các că ôp  x , y  ∈ Z p × Z p a ,b∈Z  sao N 1 E p  a , b và  cho thức      Chọn hai số nguyên và đă ôt n pq . Chọn gcd 4 a3  27 b2 , n 1 .  , N 2 E p  a , b L N 1 N 2 M 1 M 2 . p ,q e ,d ed   x , y  x , y  , M 1 Eq  a , b sao cho  Kí hiê ôu    , M 2 Eq  a , b ed ≡ 1 mod L , hê ô sẽ đúng với mọi x ∈Zn và y √ x 3  ax  b . Điều này cho phép chúng ta tiến hành mã hóa và giải mã như trong RSA gốc. xk Demytko đã đưa ra công thức tính cho x x k  , yk  k  x , y  X Y , y Z Z như sau, bằng cách đưa về tọa đô ô thuần nhất :  3 2 3 Z2i 4 Zi X i  a X i Zi  b Z i   . Hê ô thức này cho phép mã hóa văn bản thành p thành  Vành số nguyên Gauss là vành mod n ,  X i  Zi 1  X i 1 Z i  con của trường số phức   X  a  bi: a , b ∈Z , X  1,−1,i ,−i . Mô ôt phần tử q ∈ X vành được tính bởi δ  a  bi  a2  b2 . Các ước của đơn vị trong là nguyên tố khi và chỉ khi X là q là tích của ước đơn vị với mô ôt trong các phần tử có dạng sau:  α 1 i , khi đó Xk xk  . Zk ii. α . π a  bi iii. ( El-Kassar A.N., R. Hatary, Y. Awad [2], 2004) Xét vành đa thức và đặt Z p x với   f  x  g  x . h  x   hai đa thức bất khả quy s trong các vành thương p g  x , h  x ∈ Z p  x L p −1   s p −1 . Số các phần tử khả nghịch Z p  x    , . Hê ô thức có bâ ôc tương ứng là ed Z p  x    r p −1, m  x   m x  s p −1 và đúng với mọi q được gọi là phần tử nguyên tố dạng  2 2 π . π a  b 4 k  1 , khi đó là số nguyên tố thông q được gọi là phần tử nguyên tố dạng π . p là số nguyên tố thông thường có dạng q được gọi là phần tử nguyên tố dạng là mô ôt số nguyên tố. Chọn Z p  x    tương ứng là r với thường có dạng 1.3.3 RSA trên vành thương các đa thức  . C . Chuẩn trên i. và d ( El-Kassar A.N., R. Hatary, Y. Awad [2], 2004) X i Z i  1− X i  1 Z i 2  mod n , Z 2i 1 Z  r, e 1.3.4 RSA trên vành thương các số nguyên Gauss X 2i  1 4 bZ Z 2i Z 2i  1  2 Z a Z i Z i  1  X i X i  1 X  −X   là các số nguyên được chọn sao cho và sau đó giải mã X i2−a Z 2i 2−8 b X i Z 3i  mod n , X 2i    e ,d  ed ≡ 1 mod L m  x  ∈ Z  x    f  x   c  x  m  x  c x c  x  m  x  m  x  ∈Z p  x  /  f  x  , trong đó trong hệ thức Hàm Euler tại phần tử nguyên tố q có giá trị là 4 k  3 , khi đó p .  . Trong biến thể này, chọn hai phần tử nguyên tố η βγ . Khi đó khóa       φ  q δ  q −1 β ,γ ∈ X  và tính φ  η  φ  β φ  γ  δ  β −1 δ  γ −1 . Các e , d được chọn thỏa  ed ≡ 1 mod φ  η  . Văn bản m∈X c mà  δ  m  δ η sẽ mã hóa thành sẽ được giải mã bằng cách tính me ≡ c  mod η . c d ≡ m mod η . Điênh nghĩa 2.1 Môêt miền nguyên có đơn vi X được gọi là mô êt vành Euclid 1.4 Thiết lập sơ đồ cho RSA i. Bài toán lập sơ đồ cho RSA hoặc mở rộng RSA cũng là một bài toán  e 0 là các phần tử khác  δ r 0 trong đó hoă êc Ánh xaô trong định nghĩa trên thường được gọi là ánh xạ X . Phép chia Euclid trong X Tác giả Koyama K. sau đó đưa ra sơ đồ cho RSA với hàm mã hóa là một Euclid hoă ôc là chuẩn trên phân thức theo hai biến trên nhóm elliptic. mô ôt loạt các khái niê ôm tương tự như trong vành số nguyên Z . Trong phần này, chúng ta giả sử rằng 1.5 Thám mã RSA Wiener đưa ra bằng phương pháp thám mã dùng liên phân số là d n 1 4 . α ∈ X , vành thương với mỗi φ α  . Để đi đến hệ thức có nghịch đảo nhỏ, do D. Boneh và G. Durfee đưa ra [1], thực hiện được khi các ideal của d n . Y Y  là hữu hạn. Số các phần sẽ được kí hiê ôu là  φ  p . q φ  p . φ q  , trước hết là vành giao hoán có đơn vi, sao cho sẽ sinh ra là mô ôt vành Euclid và X   α  chúng tôi phát biểu mệnh đề tổng quát sau. Mệnh đề 2.1 Giả sử X X   α tử khả nghịch trong vành thương Một kết quả đáng ghi nhận khác, thực hiện bằng cách tìm nghiệm gần đúng 0.292 hoă êc δ  r  δ b . trên trường cyclotomic bởi tác giả Uematsu.Y et al.. đáng ghi nhận nhất thuộc về M. Wiener đưa ra năm 1990 [3]. Điều kiện do thì q ,r∈ X sẽ tồn tại các phần tử a bq  r sao cho f  m me được mở rộng thành hàm bậc hai Thật khó mà liệt kê ra hết các công trình thám mã RSA. Các kết quả X trong  a , b ∈ X , b ≠ 0, ii. Với theo hai biến bởi các tác giả Kobayashi K., Koyama K. hoặc mở rộng thành một đa thức bậc thỏa mãn: δ  a ≤ δ  a . δ b . Takagi trong đó đưa ra sơ đồ cho RSA với trường cơ sở là trường các số đại Q . Hàm mã hóa a ,b Nếu được nhiều tác giả khảo sát. Có thể kể ra đây các công trình của Tsuyoshi số trên  δ: X →N nếu tồn tại mô êt ánh xạ A và B là Y  A B . Khi đó ta có đẳng cấu  Y  AB ≅  Y  A ×Y  B . 4.1.3 Thám mã RSA bằng dàn hai chiều Dàn là một công cụ thám mã được nhiều tác giả nghiên cứu trong thời gian gần đây. Cách thám mã RSA bằng dàn hai chiều đã được đề cập đến trong phần 3.2.3. CHƯƠNG 2: XÂY DỰNG SƠ ĐỒ CHO RSA 2.1 RSA trên vành thương của vành Euclid Từ mệnh đề trên, chúng ta có ngay tính chất nhân tính của hàm Hệ quả  2.1 Với  α , β ∈ X mà φ  α . β  φ  α .φ  β  .  gcd  α , β 1 φ . . thì Chúng ta sẽ đi đến hê ô thức cơ bản trong RSA. Kí hiê ôu  a được dùng để chỉ phần tử chứa với a X   γ  trong vành thương a ,γ ∈ X . p ,q e ,d là các phần tử nguyên tố trong vành Euclid  gcd e , φ  pq là các số nguyên thỏa  ed ≡ 1 mod φ  pq  . Khi đó m∈X , với ed   1 và hê ê thức p ,q∈ X .Chọn số nguyên e thỏa mãn   gcd e , φ  pq −1 d ≡ e  mod φ  pq  . .Công bố n pq và e là tâ ôp con khác rỗng là tâ ôp các văn bản cần mã hóa theo X như sau. U ,V a. Tồn tại hai nửa nhóm và tính   1 b. Tồn . như khóa công khai, giữ .Văn bản là các phần tử .Văn bản Giải mã  có tính kết hợp. Chúng tôi sẽ kí hiê ôu  theo lối nhân. kiểu RSA. Chúng tôi đưa ra mô ôt số điều kiê ôn sao cho hê ô thức m ed m d μ : Y →U , và hai đồng cấu . c X   pq  . c me ∈ được giải mã bằng cách tính c m 2.1.2 So sánh với các hê ê mã RSA đã biết Hệ mã RSA gốc, các hệ mã RSA trên vành thương các đa thức và thỏa ed ≡ 1 mod L thì ed và hai nhóm  μ  X ∈U 1 ∈U 2  cho đinh nghĩa và bởi là đơn ánh. hiêuê      N i U i , Mi V i x x với mọi e ,d i1,2 và là hai số nguyên x∈X . Với các giả thiết như trong mê ônh đề trên, chúng ta có thể xây dựng trên X hê ô mã RSA như sau. Hê ê mã RSA trên nửa nhóm nhân Sinh khóa. vành thương các số nguyên Gauss trong phần 1.2 đều thuộc về sơ đồ trên. 2.2 Sơ đồ cho RSA trên nửa nhóm sao Llcm  N 1 , N 2 , M 1 , M 2  . Khi đó nếu trong X   pq  . U 1∈U , U 2∈U nhóm  θ  x   μ  x  , η  x   Kí d hai η  X ∈ V 1 ∈V 2  . θ :Y →U ×V c. Ánh xạ làm X   pq  . m∈  m được mã hóa thành tại V 1 ∈ V , V 2 ∈V khóa riêng. Mã hóa là mô ôt nửa nhóm, tức η :Y → V . φ  pq  . .Tính  sao cho với phép toán này, Y X ∈Y Giả sử là mô ôt tâ ôp khác rỗng, trên đó đã xác định mô ôt phép Mê ênh đề 2.3 Giả sử rằng 2.1.1 Sơ đồ hê ê mã hóa RSA trên vành thương của vành Euclid Sinh khóa.Chọn hai phần tử nguyên tố phân biê ôt là phép toán xảy ra trên X   pq  .  m  m sẽ đúng trong vành thương Y Giả sử toán hai ngôi Mê ênh đề 2.2 Giả sử X . 2.2.1 Sơ đồ -Tính −1 d ≡ e  mod L . -Công bố e như là khóa công khai và giữ d làm khóa riêng. Mã hóa. - X là không gian các văn bản cần mã hóa. -Mô ôt văn bản m ∈ X Giải mã. c me . được mã hóa thành d -c được giải mã bằng cách tính Mô ôt ed c m m . x 2.2.2 So sánh với các hê ê mã RSA đã biết Hệ mã RSA gốc và các biến thể của nó trong phần 1.2 đều thuộc về sơ đồ trên. phần   a b ∈ E a , b , c , d ∈Z ,0 ≤ a , b , c  p , 0 ≤ d  p2  p pc d thể viết dưới dạng x 2.3 Xây dựng biến thể của RSA End  Z p × Z p  từ 2 p phần tử, trong đó Z p× Z p 2 vào chính nó là mô ôt vành có p và hai tự đồng cấu của         a1 b 1 . p c1 d 1 a 2 b2  p c2 d 2  a 2 b2  p c2 d 2    2 1 1 1 2 2 1 2  2     Φ a π1  b σ  c τ  d π 2  1 2 1 2  1 2 1 2 2 1  2 2 1 2 xác định bởi 2  τ  x , y 0, px  . Vành p là mô êt số nguyên tố thì  2  a b pc d Như vậy, mỗi phần tử của vành 2  nhất với mô ôt ma trâ ôn kích thước 2 × 2 .    Φ : End Z p × Z p → E p đinh nghĩa 2 bởi 2 2 Z p× Z p của và Định lý 2.3 (J.J.Climent) Ánh xạ  a  a mod p b  b  mod p , p  c  c mod p  d  d mod p a b  b d  mod p  a a mod p p  c a  d c mod p  p c b  d d mod p 1 σ ,τ 2 End Z p × Z p  a π 1  b σ  c τ  d π 2 : a , b , c , d ∈ Z , 0 ≤ a , b , c  p ,0 ≤ d  là mô êt vành không giao hoán với phép cọng, phép nhân được đinh nghĩa bởi a1 b 1  p c1 d 1 π 2: Z p × Z p → Z p 2 Định lý 2.2 (J.J.Climent et.al.) Nếu p là số nguyên tố, tâ êp hợp b : a , b , c , d ∈ Z ,0 ≤ a , b , c  p , 0 ≤ d  p2 d a ,b ,c ,u ,v∈ Z p . 2 2 × 2 . Phần này sẽ tóm tắt các kết quả cần thiết về   a pc với có End  Z p × Z p  được mô tả qua hai định lý sau. vành Bergman. E p  π 1: Z p× Z p → Z p ,  là mô ôt số nguyên tố. Đến 2011, J.J. Climent et. al. Định lý 2.1 (J.J.Climent et. al.) Với b pu  v σ  x , y  y mod p ,0  5 mới thiết lâ ôp được đẳng cấu giữa vành Bergman với vành các ma trâ ôn vuông kích thước  a pc Xét các phép chiếu 2.3.1 Vành Bergman Năm 1974 Bergman đã thiết lâ ôp được kết quả tâ pô các tự đồng cấu tử  là mô êt đẳng cấu vành.  End Z p × Z p dạng  a pc 2  có thể đồng b pu  v a b a , b , c , d ∈ Z , 0 ≤ a , b , c  p ,0 ≤ d  p 2  . pc d  hoă ôc M Định lý 2.4 (J.J.Climent et.al.) a ,b ,c ,u ,v∈ Z ,0≤ a ,b ,c ,u ,v p  a pc  b ∈Ep pu  v với    là khả nghich nếu và chỉ nếu a b ∈ a q bq pqc d q cq d q a ≠ 0 và v ≠ 0 . Ep Có thể suy ra ngay số phần tử khả nghịch trong 3 p  p−1 2 là trong đó .      a b :a , b , c , d ∈ Z , 0 ≤ a , b , c  n , 0 ≤ d  n2 . nc d         a1 b 2  b 1 d 2  mod n nc b  d d 1 2 Có thể thấy rằng μ Mê ênh đề 2.5 μ và Mê ênh đề 2.6 Ánh xạ Có thể kiểm tra được rằng phép nhân, kí hiệu “.” định nghĩa bởi a1 b1 a2 b2 .  2 n c1 d 1 n c2 d2 n c1 a 2  d 1 c 2 mod n 1 2  mod n 2    trong đó ap bp p cp d p θ xác đinh bởi θ : En→ E p× Eq   là mô êt đơn ánh.  các  nhóm Ep nhân.  và  Ep và  Eq E q , khi đó Ngoài ra, tương ứng là tâ pô  Ep và kí   Eq sẽ hiệu X  M ∈ E n : μ  M ∈ E p và η  M  ∈ E q . 2 , và   a p ≡a  mod p , b p ≡ b  mod p , c p ≡ qc  mod p , d p ≡ d mod p 2  . η là các đồng cấu.  là a p , bp , c p , d p ∈ Z , 0 ≤ a p , b p , c p  p , 0 ≤ d p  p  η hoàn toàn được xác định. các phần tử khả nghịch trong μ : En→ E p a b ∈ pqc d và Bây giờ chúng ta sẽ kí hiê ôu bởi Bây giờ ta định nghĩa: 2 M ∈θ  M  μ  M , η  M  là mô ôt phép toán hai ngôi trên E n . -ánh xạ  . p , q là hai số nguyên tố phân biê ôt và n pq . Kí hiê ôu a1 a 2 mod n  a q ≡ a  mod q , b q ≡ b  mod q , c q ≡ pc  mod q , d q ≡ d mod q  2.3.2.1 Xây dựng nửa nhóm cơ sơ En a q , b q , c q , d q ∈ Z , 0 ≤ aq , b q , c q  q , 0 ≤ d q  q 2 , và 2.3.2 Xây dựng biến thể cho RSA dựa trên vành Bergman Giả sử η : En → Eq - ánh xạ Chúng tôi thiết lâ ôp hê ô thức tương tự như hê ô thức m ed m hê ô mã RSA gốc trên X trong như sau. Mê ênh đề 2.7 Nếu e,d là các số nguyên thỏa mãn các điều kiện ed ≡ 1 mod L , ed M M với mọi Llcm  p3  p−1 2 , q 3  q−12  M∈X . thì Chú ý 3.1 Mệnh đề 3.3 thật ra là hệ quả của Mệnh đề 2.3 trong đó 2.3.2.4 Thám mã 2.3.2.2 Sơ đồ hê ê mã Chúng tôi chỉ khảo sát các cánh tấn công theo kiểu chọn văn bản Sinh khóa. p , q . Tính - Chọn hai số nguyên tố phân biê ôt - Tính gốc và bằng dàn hai chiều vào hệ mã đề nghị. Hê mã chúng tôi có thể tránh n pq . được cách tấn công theo kiểu chọn văn bản trước (chosen-plaintext attack) Llcm  p3  p−1 2 , q 3  q−12  . e thỏa mãn - Chọn số nguyên  gcd  L , e 1 0 e  L  . d ≡ e−1  mod L , độ phức tạp của việc tính - Tính d là O log 3 L . n và e d như là khóa công khai, giữ làm khóa riêng. a , c , u , v ∈Z n -Chọn ngẫu nhiên thỏa   gcd  a , n 1 , gcd  v , n 1 . C d sẽ mã hóa bằng cách tính CM e  C d , m n4 1  11 n3 n4 . Xác suất này nhỏ hơn nhiều so với xác suất tương ứng của là phần tử tại vị trí 1 cách tấn công dàn thành công vào hê ô mã RSA gốc là 3 n4 . CHƯƠNG 3: THÁM MÃ RSA với a m ∈ En . nc nu  v Giải mã.-Tính tấn công dàn hai chiều vào hê ô mã chúng tôi thành công là nhỏ hơn m ∈Z n . Mã hóa.-Văn bản là các phần tử - m do có thể chọn các thành phần ngẫu nhiên trong ma trân M. Xác suất để cách 1 -Công bố  của ma trận M . Y  E n , U  E p , V  E q , U 1U 2  E p và V 1 V 2  E q . M c ,u phục được nếu đưa thêm các văn bản cần mã hóa vào 3.1 Thám mã RSA bằng dàn hai chiều 3.1.1 Đặt vấn đề Khi lập trình tấn công RSA bằng dàn hai chiều, chúng tôi phát hiện 1,2 của ma trâ ôn ra rất nhiều trường hợp dự đoán trong cách tấn công này là không đúng, tức là vector . 2.3.2.3 Độ phức tạp tinh toán trong 3.2.3 không phải là một vector ngắn nhất của dàn Từ kết quả này, chúng tôi đặt ra bài toán:“Tìm hằng số Độ phức tạp tính toán trong các quá trình mã hóa và giải mã của hệ mã chúng tôi gấp 3 lần so với hệ mã RSA gốc, Tuy vậy điều này có thể khắc t d α .n 1 4 thì t là một vector ngắn nhất của được trình bày dưới đây. α0 L . sao cho khi L ” . Kết quả sẽ 3.1.2 Điều kiện để tấn công dàn hai chiều vào RSA luôn thành công Nếu áp dụng thuật toán Gauss vào một cơ sở Bằng thực nghiệm chúng tôi nhận thấy rằng khi v 1 , v 2 của dàn hai 1 chiều L ∈ R 2 ta sẽ nhận được cơ sở thu gọn   v1 , v 2 với    ∈ v 1 ∈ ≤ ∈ v 2 ∈ . Khi đó v 1 sẽ là một vector ngắn nhất của dàn . Thật ra,  v2 L v1 , v 2 ∈ R 2 và   v1 , v 2 là cơ sở thu gọn của khi áp v 1 , v 2 . Khi đó nếu vector dụng thuật toán Gauss cho cơ sở v ∈ L , v ≠ 0 thỏa mãn ∈ v ∈ ≤ ∈  v2 ∈ mà L thì sẽ tồn tại số nguyên s  v  s v1 . vẫn là một vector ngắn L . Điều này làm chúng tôi nghĩ rằng tấn công RSA bằng p  q  2 p , chúng tôi Nếu điều kiện cân bằng được thay bằng nhận được kết quả: nếu L ∈ R2 là dàn hai chiều sinh bởi hai vector độc lập t mà dàn hai chiều vẫn còn tất định nếu thêm vào một số điều kiện nào đó. là vector có độ dài nhỏ nhất trong số các vector của dàn Mệnh đề 3.1 Giả sử thì tỷ lệ tấn công được rất cao, tức là nhất của dàn L độc lập tuyến tính với  v1 . tuyến tính d ≈n4 d n 1 4 d 1 √ 4  2 √2 1 n4 thì t là một vector ngắn L . nhất của dàn 3.2 Bài toán DLP trên nhóm GL 2, p 3.2.1 Đặt vấn đề Bài toán logarit rời rạc (DLP-discrete logarithm problem) được quan tâm ngay từ khi giao thức trao đổi khóa Diffie-Hellman ra đời. Có rất nhiều công trình khảo sát các phương pháp giải bài toán DLP trên một Bây giờ xét hệ mã RSA với các kí hiệu thông thường và với điều kiện cân trường hữu hạn cho trước. Việc áp dụng các phương pháp này giải bài toán DLP trên nhóm nhân các ma trận còn rất phức tạp do mất nhiều tính toán. bằng 1 √ n p , q  2 √ n . Chúng tôi đạt được kết quả sau. 2 3.2.2 Bài toán DLP trên nhóm Giả sử p là số nguyên tố, 1 Mệnh đề 3.2 Nếu dàn 2 d n4 √ 29 thì t là một vector ngắn nhất của GL 2, p là nhóm nhân các ma trận vuông cấp 2 không suy biến hệ số trên Z p . Bài toán DLP trên GL 2, p là bài toán: L . 3.1.3 Nhận xét về phương pháp tấn công RSA bằng dàn hai chiều GL 2, p Bài toán: “cho “. A , B ∈GL 2, p  , hãy tìm số nguyên k mà k A B (3.4) Nghiệm k của bài toán nếu tồn tại sẽ được xác định duy nhất theo modulo d với d là bậc của ma trận A trong nhóm GL 2, p . A Giả sử là I   1 0 0 1 a11 a12 a21 a22   , B  b11 b12 b21 b22  , ma trận đơn vị sẽ kí hiệu b. z 1  z 2 : Kí hiệu (i) . 3.2.3 Ý tương với nhận xét rằng việc giải bài toán (3.4) sẽ đơn giản hơn rất nhiều khi A là ma trân chéo, chúng tôi dựa vào dạng chéo Jordan của A để làm đơn giản hóa việc giải bài toán (3.4).   Việc đưa ma trận A về dạng chéo Jordan bao gồm tìm một ma trận  P−1 AP . Chúng tôi tóm tắt lại như sau. Đa thức theo một biến z   ρA  z det  A− zI  a11 − z   a22− z −a 12 a 21 ρA  z  được gọi là đa thức đặc trưng của ma trận A. Nếu Z p , ta sẽ mở rộng nghiệm trong ρA  z  Như vậy để được trường mở rộng ρA  z  Zp không có theo một nghiệm α của  luôn có 2 nghiệm z1 , z 2 (trong Zp hoặc     p21  p22  p11 p 12 p 21 p 22 (ii) r 10 : Khi đó cơ sở của p 11 p 12 D và   z1 1 0 z1 p21 p22   , . N  A− z 1 I    dim N A− z 1 I và P sẽ được xác định bởi  là D  p11 p12  2 . Ta tìm 2 vector   z1 0 0 z1  3.2.5 Thuật toán đưa bài toán DLP trên a. z 1 ≠ z 2 : và  và P p21 p22  . Các ma trận D p11 p 12 p 21 p 22  . GL 2, p về trường cơ sơ Lũy thừa của ma trận dạng chéo Jordan có thể tính được như sau. -Ta tìm các vector riêng -Khi đó  I Z p  α  a α  b: a , b ∈ Z p  . Z p α  ). Có các trường hợp sau. D P 1 r 2 0 . Ta tìm một phần tử R  A− z 1 I  . Khi đó tồn tại phần tử của  A− z mà và một ma trận dạng chéo Jordan D sao cho D r 11 : Trong trường hợp này, p11 ≠0 p12 3.2.4 Chéo hóa Jordan của ma trận P ∈GL 2, p  A− z 1 I i i ∈ N  , có 2 trường hợp: r i rank   z1 0 0 z2  p i 1 pi 2 t ứng với giá trị riêng  và P  p11 p 12 p 21 p 22  z i i1,2 . Mệnh đề 3.6 Với k là số nguyên dương ta có: a. Nếu D b. Nếu D .    z1 0 0 z2 z 1 0 z thì thì Dk Dk   z 1k 0 0 z k2  z k k z k−1 0 zk . . Bài toán (4.4) ban đầu có thể đưa về dạng đơn giản hơn như sau. −1 k −1 k PD P   B ∈ P D P  B  4.4 ∈ −1  −1 Do ma trận D k tính theo mệnh đề trên, ta Nếu D đồng nhất các thành phần tương ứng trong 2 ma trận ở hai vế của (3.5) để có một hệ 2 phương trình theo k mà mỗi phương trình là bài toán DLP trên Zp (hoặc trên trường mở rộng A đây khẳng định bậc của của Z p α Z p ). Mệnh đề sau của có thể tính được theo các bậc của các phần tử D . A ∈GL 2, p Khi đó: D (b) Nếu D (c) Nếu D D và D Nếu D      Thuật toán  z1 0 0 z2 z 1 0 z z 0 0 z  thì thì thì    ord  A  ord  z   Kiểm tra xem ρA  z  có nghiệm trong F  Z p α  ρA  z  . Xác định ma trận P sao cho chéo hóa Jordan của A.  −1 AP .  với z 1 0 z  z 1 , z 2 ∈ F , z 1 ≠ z 2 : sang Bước 2. với z ∈ F : sang Bước 3. với z ∈ F : sang Bước 4. c 21 ≠ 0 hoặc c 12 ≠ 0 : bài toán vô nghiệm. Kết thúc.   z 1k c 11 , kết quả có dạng z k2  c 22 k  m1 mod l 1  với l i ord z i i1,2 . k m2 mod l 2   m  1−m2 ∈ gcd l 1 , l 2  : nghiệm của (4.4) được tính theo  -Ngược lại, bài toán (4.4) vô nghiệm. Kết thúc. Bước 3. Nếu a22− z −a 12 a 21 . hay không. Nếu có đặt α   . định lý Trung Hoa mở rộng. .   Zp z 0 0 z với Ngược lại, giải từng phương trình của hệ -Nếu ord  A  p . ord  z  . ρA  z det  A− zI  a11 − z F  Z p , ngược lại đặt   D P ord  A lcm ord z 1 , ord z 2  . Bước 1. Tính  z1 0 0 z2  c11 c12 c 21 c22 là ma trận chéo hóa A , tức tồn tại ma trận không suy biến P mà Jordan của (a) Nếu Nếu  Bước 2. Nếu Mệnh đề 3.7 Giả sử −1 C  P BP , giả sử C  k ∈ P BP  D . (3.5) là tính được và P BP Tính ma trận là một nghiệm của D P−1 AP với D là dạng c 21 ≠ 0 hoặc c 12 ≠ 0 hoặc c 11 ≠ c22 : (4.4) vô nghiệm. Kết thúc. Ngược lại giải bài toán k z c 11 trong F . Nghiệm tìm được là nghiệm của (4.4). Bước 4. Nếu c 21 ≠ 0 hoặc c 11 ≠ c22 : bài toán vô nghiệm. Kết thúc. Ngược lại, bài toán (4.4) đưa về việc giải hệ theo ẩn k :  KẾT LUẬN z k c11 .  4.6 k z k−1 c 12 Nếu z 0 thì việc giải hệ (4.6) là tầm thường. Khi 4.6 ∈ Giải (4.7)   z ≠ 0 , ta biến đổi đóng góp vào việc nghiên cứu RSA, luận án đã đạt được những kết quả sau: z k c 11 ∈ z k c 11 4.7 k c11  z c12 4.8 k z k  z c 12 bằng các phương pháp đã RSA là một hệ mã được dùng rộng rãi nhất trong mã hóa thông tin. Để - biết ta được này bao quát được RSA trên vành thương các đa thức và vành nghiệm thương các số nguyên Gauss của tác giả El-Kassar A. N., R. Hatary k ≡ s  mod l  trong đó l ord  z  . F , nếu nghiệm Giải (4.8) trong trường k ∈Z p thì (4.4) vô nghiệm. phần dư Trung Hoa giải hệ  - k ≡r mod p . Dùng định lý Ngược lại, nghiệm của (4.8) có dạng - 3.2.7 Nhận xét (4.4) thì phải cần xấp xỉ √ p − p 2  2  p −1 ≈ p 2 theo thuật toán của chúng tôi, chỉ cần giải nhiều nhất 2 bài toán DLP F có nhiều nhất √ p2 p 2 giá trị (khi công và đưa ra thuật toán nhằm đơn giản hóa việc giải bài toán DLP bước và lưu trữ xấp xỉ chừng ấy giá trị. Trong khi đưa bài toán về bài toán DLP trên trường F  Z p α  ), điều Climent, P. R. Navarro và L. Tortosa. Trong lĩnh vực thám mã RSA, đưa ra điều kiện của khóa riêng bảo đảm cho phương pháp tấn công RSA bằng dàn hai chiều luôn thành Nếu áp dụng trực tiếp phương pháp bước nhỏ, bước lớn để giải bài toán trên trường trong luận án. Dựa trên sơ đồ cho RSA trên nửa nhóm, xây dựng một biến thể mới cho RSA dựa trên kết quả về vành Bergman của các tác giả J. J. nghiệm nhận được chính là nghiệm của (4.4). F và Y. Awad. Xây dựng sơ đồ cho RSA trên một nửa nhóm, đây là sơ đồ tương đối tổng quát, bao quát hết tất cả các biến thể của RSA được đề cập - k ≡ s mod l , k ≡ r mod p Xây dựng sơ đồ cho RSA trên vành thương của vành Euclid, sơ đồ trên nhóm GL(2,p). Trong quá trình thực hiện luận án, tác giả thấy rằng còn có những bài toán liên quan đến luận án như sau: - Trước khi tìm được tài liệu về vành Bergman, tác giả đã cố gắng xây bước và lưu trữ xấp xỉ chừng ấy giá trị. Rõ dựng một biến thể của RSA trên vành thương của vành quaternion, ràng chi phí sẽ giảm đi rất nhiều khi p lớn. Ngoài ra việc vét cạn để tìm ra tuy có đạt được một số kết quả nhưng chưa hoàn thành mục đích do này sẽ thực hiện xấp xỉ cấp của A trong GL 2, p toán hơn việc tìm ra cấp trong F theo Mệnh đề 4.7 sẽ mất nhiều tính của z 1 và z2 . - vành quaternion không giao hoán. Cách thám mã dùng thuật toán LLL của D. Boneh và G. Durfee [22] cũng là heuristic. Như vậy, tương tự như cách tấn công RSA - dùng dàn 2 chiều, có thể tìm các điều kiện đảm bảo cho phương toán Ben-Or [50], thuật toán Cantor-Zassenhaus [67]…nên biến thể của pháp tấn công này luôn thành công. Giữa liên phân số và dàn có mối liên hệ mật thiết. Như vậy thông RSA trên vành thương các đa thức trong phần 1.3.3 có thể bị thám mã hoàn toàn nếu áp dụng các thuật toán này. qua cách tấn công RSA bằng dàn, có thể chỉ ra cách tấn công tương - bit nên RSA trong phần 1.3, một câu hỏi thú vị được đặt ra là liệu nó có bao modulus được áp dụng cho số - n phải có độ lớn 1024 bit. Như vậy thuật toán phân tích n có độ lớn 1024 bit. m ∈ M l n m có độ dài 1024 bit. Do nhóm giao hoán thì có thể áp dụng được sơ đồ này. Tuy vậy chúng nên tôi vẫn chưa có kết luận gì cho một hệ mã RSA xây dựng trên một không quá 256 bit. Vì mỗi phần tử này thuộc nửa nhóm và sẽ tiếp tục công việc này trong tương lai. Đối với biến thể của RSA được xây dựng ở Chương 2, các quá trình không quá 256 bit. Việc phân tích mã hóa và giải mã đòi hỏi nhiều tính toán. Bài toán đặt ra là thiết lập hơn. Cuối cùng, như một kết luận cho luận án, chúng tôi sẽ so sánh sự an toàn của hệ mã RSA với các biến thể của nó dưới khía cạnh thám mã bằng cách phân tích modulus. Để đơn giản cho việc phân tích, chúng tôi giả sử rằng độ dài của mỗi văn bản là 1024 bit và thuật toán phân tích modulus n là thuật toán vét cạn. Trước hết, do có rất nhiều thuật toán hiệu quả phân tích một đa thức cho trước f  x ∈ Z p  x  như thuật toán Berlekamp [49], thuật có ít nhất 4 phần tử, do đó mỗi phần tử của n Zn nên m có độ dài n có độ dài trong trường hợp này đơn giản Đối với hệ mã RSA trên vành thương các số nguyên Gauss, mỗi văn bản thời gian, sẽ khảo sát các vấn đề trên một cách tỉnh táo và toàn diện m là một ma trận vuông hơn nhiều so với hệ mã RSA gốc. công thức trước sao cho có thể tiết kiệm được việc tính toán. Tác giả hy vọng rằng trong thời gian sắp tới, khi không còn bị áp lực có độ dài 1024 Đối với biến thể của RSA trên vành ma trận, mỗi văn bản quát được các hệ mã RSA trong tương lai hay không ? Chúng tôi đã chứng minh được rằng nếu một hệ mã RSA được xây dựng trên một m ∈Zn Đối với hệ mã RSA gốc, do mỗi văn bản ứng bằng cách dùng liên phân số và ngược lại. Mặc dù sơ đồ RSA đưa ra ở phần 2.2 bao quát hết các biến thể của ma  bi có độ lớn 1024 bit nên 512 bit. Do đó độ lớn của bit. Do bit. Nếu ηl ik l , k ∈ Z  η l ,k và b đều có độ lớn δ  m a 2  b 2 không thể vượt quá 1025 m ∈Z  i    η quá 1025 bit, vì vậy  a nên δ η  không vượt quá 1025  δ  η l 2  k 2 thì không vượt không vượt quá 256 bit. Việc phân tích bằng thuật toán vét cạn chưa hẳn đơn giản hơn trong trường hợp phân tích modulus của hệ mã RSA gốc. Tuy nhiên, mặc dù các tính toán trong quá trình mã hóa và giải mã trong trường hợp này được thực hiện trong vành thương Z i  Z  i   η  , thực tế sẽ được tính trên và sau đó lấy modulo theo η (bằng cách thực hiện phép chia cho η ). Nhưng do phép chia Euclid trên không duy nhất nên việc giải mã tính khác me d Z i  thực hiện có thể cho ra kết quả m . Điều này cho thấy để xây dựng hệ mã RSA trên vành Z  i   η  , trước hết cần xây dựng một hệ đầy đủ và thương duy nhất X Z i  cho DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ các phần dư có thể có trong phép chia một phần tử trong η , X chính là không gian các văn bản cần mã hóa không phải đơn giản và đây [1 Long T.D., Thu T.D., Thuc N.D., “A General Model for RSA có thể là lý do vì sao biến thể của RSA trong trường hợp này ít được ] Cryptosystem”, ICTFIT’10, Tuyển tập công trình nghiên cứu trong trường hợp này. Việc xây dựng X Công Nghệ Thông Tin & Truyền thông 2010, pp. 100-103. dùng đến. Đối với hệ mã RSA trên nhóm đường cong elliptic, mỗi văn bản là một phần tử x ∈ Z n , do đó n 1024 bit. Việc phân tích modulus sẽ có cùng kích thước với n x là [2 Long T.D., Thu T.D., Thuc T.D., “Bài toán DLP trên nhóm ] GL(2,p)”, ICTFIT’12, Tuyển tập công trình nghiên cứu Công trong trường hợp này hoàn toàn Nghệ Thông Tin và Truyền thông 2012, pp. 19-26. như trong hệ mã RSA gốc. Tuy nhiên độ phức tạp tính toán trong các quá trình mã hóa và giải mã trong trường hợp này là lớn hơn nhiều so [3 Thuc D. Nguyen, Than Duc Nguyen, Long D. Tran, “Attacks on với hệ mã RSA gốc. Đối với hệ mã RSA gốc, mã hóa ] low private exponent RSA: an experimental study”, 2013 13th e c ≡ m  mod n cần phải thực hiện xấp xỉ log 2 e theo thuật toán lũy thừa nhanh. Đối với hệ mã RSA trên nhóm đường cong elliptic, các công thức ở phân 1.2.2 chỉ ra để tính thức mã hóa  e  x , y  s , t International Conference on Computational Science and Its phép nhân s trong công Applications (ICCSA2013), pp.162-165, IEEE, 2013. [4 ] cần thực hiện ít nhất xấp xỉ cryptosystem analogue of RSA”, 2013 International Conference 5 log 2 e phép toán. Các phân tích trên đây chỉ ra rằng, với cùng một modulus on IT Convergence and Security, IEEE Ebook, pp. 377-380. n , việc thiết lập hệ mã RSA gốc là đơn giản và an toàn hơn các biến thể của nó. Điều này giải thích phần nào hệ mã RSA gốc được dùng rộng rãi hơn các biến thể của nó. Long D.T., Thu D.T., and Thuc D.N., “A Bergman ring based [5 Long T.D., Thu T.D, Thuc D.N., “On the heuristic guess of 2- ] dimension lattice attack on low private exponent RSA, Tạp chí Khoa học-Khoa học Tự nhiên & Công nghệ, Đại học Sư phạm Tp Hồ Chí Minh, số 2(67, 2015, pp. 101-108. TÀI LIỆU THAM KHẢO CHÍNH [1] D. Boneh and G. Durfee (1999), “Cryptanalysis of RSA with private key d less than N0.292”, Proc. of Crypto’99, LNCS, vol. 1666, IACR, Springer-Verlag, 1999. [2] El-Kassar A.N., R. Hatary and Y. Awad (2004), “Modified RSA in the domains of Gausian integers and polynomials over finite fields”, Proc. Intl. Conf. Computer Science, Software Engineering, Information Technology, e-Business and Applications (CSITeA’04), Cairo, Egypt. [3] M. Wiener (1990),” Cryptanalysis of short RSA secret exponents”, IEEE Transactions on Information Theory 36, pp.553-558. [4] N. Demytko (1993), “A new elliptic curve based analogue of RSA”, EUROCRYPT’93, LNCS 765, pp. 40-49. [5] R. L. Rivest, A. Shamir, and L. M. Adleman (1978), “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Communications of the ACM 21, no 2, 120-126. [6] Varadharajan V. and Odoni R (1985), “Extension of RSA cryptosystems to matrix rings”, Cryptologia, 9:2, 140-153, 1985.