Luận văn Giải thuật mã hoá mật mã RSA

ät văn bằng mới cùng khóa, và tất cả những chữ ký mới sẽ được điểm trên văn bằng mới thay cho cái cũ. Tuy nhiên, sự việc phần cứng máy tính tiếp tục cải tiến chỉ rõ cho việc thay thế những khóa hết hạn với những khóa mới và dài hơn vài năm. Việc thay thế khóa co phép người ta thấy được mối thuận lợi của cải tiến phần cứng để gia tăng tính bảo mật trong hệ thống mã hóa. Phần cứng nhanh hơn đã ảnh hưởng đến việc gia tăng bảo mật, có lẽ mênh mông nhưng chỉ nếu chiều dài khoá được gia tăng thường xuyên. Nếu chẳng may khóa bí mật của bạn bị mất hay bị phá hủy nhưng không bị xâm hại, bạn có thể không ký dài hơn hay giải mã những thông báo nhưng vài cái trước đó đã được ký với khóa bị mấtvẫn có giá trị. Đềiu này có thể xảy ra, ví dụ nếu bạn quên mật khẩu được sử dụng để try cập khóa của bạn hay nếu ổ cứng mà trên đó khóa được lưu trữ đã bị hư hại. Bạn cần phải chọn một khóa mới đúng ngay lập tức, để giảm mức tối thiểu số những thông báo mọi người gửi bạn đã mã hóa dưới khoá cũ của bạn, những thông báo bạn không cần thiết phải đọc. Các vấn đề sẽ xảy ra nếu khóa của bạn bị xâm nhập: Nếu chẳng may khóa bí mật của bạn bị xâm nhập đó là nếu bạn nghi ngờ một kẻ tấn công có thể chứa khóa bí mật của bạn thì bạn phải làm bộ để vài kẻ địch của bạn có thể đọc được những thông báo được mã hóa gửi đến bạn và giả mạo tên bạn trên những tài liệu. Những hậu quả nghiêm trọng kèm theo tính chất quan trọng của việc bảo vệ khoá bí mật của bạn với những cơ cấu mạnh cực kỳ. Ngay lập tức bạn phải khai báo với nơi cấp ăn bằng và đưa khoá cũ của bạn vào CRL; ở đó sẽ thông báo cho mọi người là khoá đã bị giả mạo. Sau đó chọn một khóa mới và thu được những văn bằng thích hợp với nó. Bạn có thể sử dụng khóa mớiđể ký lại những tài liệu mà bạn đã ký với khóa bị tổn hại; những tài liệu đã được định thời gian tốt như được ký vẫn còn có giá trị. Bạn cũng nên thay đổi cách lưu trữ khoá bí mật của bạn ngăn chặn sự xâm phạm khóa mới. Xâm nhập vào hệ thống RSA. Có một vài cách hiểu của việc “bẻ gãy” RSA. Cái nguy hiểm nhất là có thể một kẻ tấn công phát hiện ra khóa bí mật tương ứng với khóa công khai; đây là đềiu cho phép kẻ xâm nhập có thể đọc tất cả các thông điệp đã được mã hóa với khóa công khai và chữ ký giả mạo. Hiển nhiên đây là cách việc tấn công này là lấy thừa số của môđun công khai n, dựa vào hai thừa số số nguyên tố là p và q. Từ p và q và e, là số mũ chung, kẻ xâm nhập có thể dễ dàng lấy được d là khoá bí mật. Phần khó khăn nhất việc phân tích ra thừa số của n, bảo mật RSA dựa trên việc phân tích thành thừa số là rất khó. Thực tế tác vụ của việc tìm lại khóa bí mật tương đương với tác vụ phân tích thừa số môđun: bạn có thể sử dụng d để phân tích ra n cũng như việc phân tích thừa số n để tìm ra d. Cách khác để “bẻ gãy”RSA là tìm ra một kỹ thuật tính tóan căn thứ e () chia n lấy dư. Vì c= me nên là thông báo m. với cách tấn công này cho phép bất kỳ ai cũng có thể phục hồi những thông báo đã mã hoá và những chữ ký giả mạo mà không cần biết khóa bí mật. Hiện nay chưa có phương thức nào có thể bẻ khóa RSA bằng cách này. Những tấn công được đề cập phải là cách duy nhất để bẻ khóa RSA như cách có thể phục hồitất cả các thông báo được mã hóa dưới một khóa lấy được. Tuy nhiên có những phươngthức khác có mục đích là phục hồinhững thông báo đơn giản. Thành côngnhưng không cho phép những kẻ xâm nhập có thể phục hồinhững thông báo khác cùng một khóa. Tấn công một thông báo riêng lẻ đơn giản nhất là tấn công vào những văn bản được đoán trước. Một kẻ xâm nhập có thể thấy văn bản mã hóa việc tấn công đó dường như là “tấn công lúc bình minh” và mã hóa ước đoán này với khóa công khai của người nhận, bằng cách so sánh với văn bản mã hóa thực tế, kẻ xâm nhập biết được trong bất cứ trường hợp nào ước đoán đó đúng. Việc tấn công nào có thể bị ngăn cấm bởi việc thêm nhiều bít ngẫu nhiên vào thông báo. Tấn công vào thông báo riêng lẻ khác có thể xuất hiện nếu một ai đó gửi thông báo đến ba người, người mà có số mũ công khai là e =3. Kẻ tấn công biết được điều này và thấy ba thông báo đó có thể phục hồi thông báo đó, cách tấn công này và cách để ngăn chặn nó đã được thảo luận bởi Hastad. Tất nhiên cũng có nhiều kiểu tấn công nhắm không chỉ nhắm vào bản thân RSA mà còn đưa ra những bổ sung cho RSA; điều này không tính như “ “ bẻ gãy”RSA” bởi vì nó không phải là những yếu điểm của giải thuật RSA bị khai thác, nhưng là một yếu điểm trong những bổ sung đặc biệt. Chẳng hạn như, nếu một ai đó lưu trữ khóa bí mật của anh ta một cách lơ là không an toàn thì một kẻ tấn công có thể phát hiện ra đều này. Một người nào đó không thể nhấn mạnh một cách mạnh mẽ đích thực những yêu cầu bảo mật RSA một bảo mật bổ sung, về mặt toán học (bảo mật các giới hạn, chẳng hạn như chọn kích thước chiều dài khóa, nhưng khôn g đủ. Trong thực tế, hầu hết những vụ tấn công thành công sẽ giống như đích tại những nơi bổ sung không bảo mật và tại những giai đoạn quản lý khóa của hệ thống RSA. Những tấn công vào hệ thống RSA. Một giải thuật mũ số môđun RSA có thể ngắt hệ thống mã hoá và cho phép một vài thông báo giải mã được. Tuy nhiên, cũng có nhiều cuộc tấn công tinh vi mà không đòi hỏi số mũ môđun. Họ có thể không có kết quả trong việc bẻ gãy hệ thống mật mã RSA nhưng trong vài trường hợp đặc biệt họ có đủ thông tin để giải mã được một số thông báo. Ta có thể xem xét 4 loại tấn côngvào hệ thống mật mã RSA. 1 Lạm dụng quá nhiều RSA. 2 Những tấn côngvào số mũ bí mật quá thấp 3 Những tấn côngvào số mũ công khai quá thấp ( truyền đi rộng quá) 4 Tấn côngvào những bổ sung Ta biết là giá trị tướng ứng từ p và q. Rõ ràng hơn, có p và q ta có thể tính , cũng như thế ta có thể tính p và q dựa trên phương trình tương ứng. (1) Và chú ý rằng ta có hai phương trình và không biết cả hai (vì n là do người khác đưa ra). Cũng như thế, khóa bí mật d là phương trình biết được mũ số môđun RSA, p và q. khi biết được p và q ta có thể biết được d dựa trên định nghĩa: . Và k = (ed -1)/ 2s, k là một số chứa lặp cơ số 2 chia cho ed -1 và ta có được số dư và s là số lần ta chia. Bổ đề: với mọi số nguyên a, số nguyên tố n, được sắp xếp trong :ak+n Z và thuộc nhóm (Z / n Z)* là: . (ak+n Z là số nhỏ nhất, / (ak+n Z)l = 1+ nZ ) Chứng minh: lấy một số nguyên là số nguyên tố n, bằng định lý giải mã RSA Vì ed-1 = k2s, ta có: . Do đó: (ak+n Z)2s = 1+ nZ. Lặp lại (ak+n Z)2s = 1+ nZ nếu và chỉ nếu 2s được chia bởi ak+n Z trong nhóm (Z / n Z)* Cho nên ak+n Z thuộc nhóm (Z / n Z)* chia cho 2s Định lý: lấy a là một nguyên là số nguyên tố cùng với n. Nếu ak khác bậc chia lấy dư cho p và q thì , với Chứng minh: bằng những kết quả trước đó, và name trong khoảng . WOOLOG cho rằng lớn hơn . Lấy 2t thuộc , và t < s, nhưng . Cho nên . Giải thuật trên cho phép có thể được sử dụng để lấy lại p và q để đưa ra e, d và n. ( chú ý rằng có ba lỗi trong giải thuật được thể hiện trong phần này.) Ví dụ: Chúng ta sẽ tính n =253, e= 3 và d= 147. Do đó, ed -1 = 440, k=55 và s=3. 1. Chọn một số nguyên a ngẫu nhiên trong chuỗi . Ta lấy ( a=2). 2. Tính toán . Nếu g > 1 thì g =p hay g=q và ta tính được thừa số n.( ) 3. nếu g = 1 thì tính toán với cho đến khi hay t = 0.(, .) 4. Nếu n>g>1 thì g=p hay g = q. Từ đây, thừa số của n được tìm thấy và giải thuật kết thúc. Nói cách khác, giải thuật không thành công với việc lựa chọn dựa trên a (n= 23x11=253). Nếu giải thuật không thành công với việc chọn a thì chúng ta chạy nó lại một lần nữa. Định lý: số lượng số nguyên tố a đến n trong đoạn {1, 2, …n} với mỗi ak có một và khác nhỏ nhất tại (p-1)(q-1)/2 Định lý bao hàm xác suất thành công của giải thuật là tại ½. Do đó, xác suất thành công sau r là tại 1- 1/2r. Lạm dụng: Một ví dụ của một tấn công lạm dụng hiển nhiên là môđun chung. Giả sử rằng một người phòng ngừa việc sử dụng môđun khác n=pq cho mỗi người sử dụng và sử dụng một n cố định. Thay vì mỗi người sử dụng lấy một khóa công khai (n, ei) và một khoá bí mật riêng tư di.. Tuy nhiên Bob có hể sử dụng khóa bí mật mà anh ta sở hữu db để tính toán thừa số n. Một khi anh ta tìm ra p và q anh ta có thể số mũ khóa công khai của Alice để tìm ra mũ số riêng tư của cô ta. Mũ số bí mật thấp Để giảm bớt thời gian giải mã, một người có thể sử dụng d nhỏ. Tuy nhiên những kết quả này nằm trong toàn bộ việc bẽ gãy hệ thống mã hoá. Định lý: lấy n=pq với q<p<2q. Lấy . Ta có (n, e) với , thì những kẻ tấn công có thể thu hồi được d một cách hiệu quả. Đó là một vấn đề khi có d thì có thể thu hồi nếu . Mũ số công khai thấp. Để giảm thời gian mã hoá, e thường xuyên được chọn là 3. Tuy nhiên, những tấn công thất bại con số e = 216 + 1 = 65537 được đề nghị sử dụng. Với e này, chỉ với phép tính mũ 16 và một phép tính nhân cần thiết để mã hoá việc mũ hóa nhanh. Tấn công khắp nơi đòi hỏi Bob gửi một bản sao e của những thông báo tương tự sử dụng nhiều môđun RSA khác nhau. Trong trường hợp này, kẻ tấn công có thể tính toán hiệu quả những thông báo gốc. Do đó, việc tạo ra e lớn hơn số lượng thông báo để vô hiệu tấn công này. Thi hành. Những khác nhau giữa kiểu tấn côngđầu tiên, việc lạm dụng RSA và những tấn công trong việc thực thi là tính tinh vi của tấn công. Những tấn công vào việc thực thi tương đương với những điều ngoài phim gián điệp. Xem xét những thẻ thông minh lưu trữ khoá RSA bí mật. Bằng sự tìm tòi lấy thẻ thông minh để thực hiện một giải mã RSA, một kẻ tấn công có lẽ có thể phát hiện mũ số giải mã bí mật d. Ngoài ra d cũng có thể thường xuyên bị phát hiện bởi việc đo lường sức mạnh việc tiêu thụ của thẻ thông minh. Chương 2: Tìm hiểu về RSA. 1. Định nghĩa RSA: Năm 1977, Ron Rivest, Adia Shamir và Leonard Adleman đã đưa ra hệ thống mã hóa dữ liệu dùng khóa công khai. Được làm việc theo nguyên tắc sau: chọn hai số lớn số nguyên tố là p và q, và tính theo công thức n= pq, n được gọi là môđun. Chọn một số e nhỏ hơn n, và số này có giá trị tương đối là (p-1)(q-1), và tìm ra số nghịch đảo của chúng, đó là d, mod (p-1)(q-1). Có nghĩa là ed = 1 mod (p-1)(q-1), e và d được gọi là số mũ chung và số mũ riêng tương ứng. Khóa công khai là một cặp (n, e) và khóa bí mật là d. Thừa số p và q phải được giữ bí mật hoặc làm mật hiệu quả khi sử dụng lần sau. Thật khó đoán để có thể tìm ra được khóa bí mật d từ khóa chung (công khai) (n, e). Tuy nhiên nếu ai đó có được n dựa trên p và q thì có thể tìm ra khóa bí mật d. Như thế toàn bộ việc bảo mật của RSA được căn cứ vào sự xác nhận việc phân tích ra thừa số nguyên tố là rất khó. Đó là cách RSA làm việc cho việc bảo mật riêng rẽ và chứng minh xác nhận. Bảo mật RSA (mã hóa): giả sử rằng Alice muốn gửi một thông báo riêng tư là m đến cho Bob. Alice tạo ra một văn bản mã hóa được biểu diễn dưới dạng mũ c = m^e mod n, có e và n là khóa công khai của Bob. Để mã hóa, Bob cũng phải giải mã hàm mũ m = c^d mod n, và chuyển đổi lại thành thông báo nguyên thuỷ m. phải chắc chắn rằng mối quan hệ giữa e và d phải đúng thì Bob mới có thể chuyển đổi chính xác thông báo đó được. Vì chỉ có Bob mới biết được d, và do đó cũng chỉ có Bob mới có thể giải mã được. Chứng minh xác thực của RSA: giả sử Alice muốn gửi một tài liệu mật hiệu m đến cho Bob. Alice tạo ra một chữ ký kỹ thuật số và cũng được biểu diễn dưới dạng mũ s = m^d mod n, mà d và n cặp khóa của Alice. Cô ta gửi s và m đến cho Bob. Để kiểm tra chữ ký có đúng hay không, Bob phải giải hàm mũ và kiểm tra lại thông báo đã được chuyển đổi trở lại, m = s^e mod n. Cặp khóa công khai của Alice là e và n. Đó là lý do mà việc mã hóa và chứng nhận không cho phép chia sẽ bất kỳ khóa bí mật lẽ nào: mỗi người chỉ có khóa công khai chung của riêng họ và anh ta hay chị ta sở hữu riêng biệt khóa bí mật của họ. Bất cứ người nào có thể gửi một thông báo đã được mã hóa hoặc kiểm tra thông báo mật hiệu (có sử dụng chữ ký kỹ thuật số) thì họ chỉ sử dụng khóa công khai đó nhưng chỉ người nào đó có quyền sở hữu đúng khóa cá nhân thì mới có thể giải mã được thông báo mật hiệu đó. Các khóa công khai và khoá bí mật chỉ định các hàm có thể áp dụng cho bất kỳ thông báo nào. Cho D thể hiện tập hợp các thông báo chấp nhận được. Ví dụ D có thể là tập hợp tất cả dãy bít có chiều dài hữu hạn. Ta yêu cầu các khóa công khai và khóa bí mật chỉ định các hàm từ D đến chính nó. Chẳng hạn như, ta thể hiện các khóa công khai và riêng của Alice và Bob lần lượt là PA, SA và PB, SB. Hàm tương ứng với khóa công khai PA của Alice được ký hiệu là PA() và hàm tương ứng với khóa bí mật SA được ký hiệu là SA(). Như vậy các hàm PA() và SA() là các phép hoán vị của D. Các khoá công khai và bí mật của một bên tham gia bất kỳ là một “ cặp vừa khớp” ở chổ chúng chỉ định các hàm là nghịch đảo với nhau. Nghĩa là: M = SA(PA(M)) M= PA(SA(M)) Với một thông báo M D việc biến đổi thành công M bằng hai khoá PA và SA theo một trong hai thứ tự sẽ cho ra thông báo M trở lại. Trong hệ mật mã này nhất ngoài Alice ra không ai có thể tính toán hàm SA() trong thời gian cho phép được. Tính riêng tư của thông báo được mã hóa và gửi đi và các số ký danh của Alice đều dựa vào giả thiết cho rằng chỉ Alice mới có thể tính toán được SA(). Yêu cầu này cho biết tại sao Alice phải giữ bí mật SA. Giả sử chí có Alice mới có thể tính toán SA() phải đứng cvững cho dù mọi người biết PA và có thể tính toán PA(), hàm nghịch đảo với SA() một cách hiệu quả. Ta có thể thể hiện phép biến đổi PA() nhưng không thể hiện cách biến đổi nghịch đảo SA() tương ứng. 2. Trình tự của một hệ mật mã RSA. Trong hệ mã khóa công khai RSA, một bên tham gia tạo các khoá công khai và khoá bí mật của mình theo thủ tục sau đây: Lựa chọn ngẫu nhiên hai số nguyên tố lớn p và q. Các số nguyên tố p và q có thể là, giả sử, 100 chữ số thập phân cho mỗi số. Tính toán n theo phương trình n=pq. Lựa chọn một số nguyên lẻ nhỏ e là nguyên tố cùng nhau với Þ(n)= (p-1)(q-1) Tính toán d dưới dạng nghịch đảo nhân của e, môđun Þ(n). Công khai cặp P= (e, n) dưới dạng khóa công khai RSA của mình. Giữ bí mật cặp S =(d, n) làm khóa bí mật RSA của riêng anh ta. Với những bước trên ta xác định được: - Miền xác định D là tập hợp Zn - Phép biến đổi một thông báo M kết hợp với một khóa công khai P= (e, n) là: P(M) =Me ( mod n) - Phép biến đổi của một văn bản mật mã C kết hợp với một khóa bí mật S=(d, n) là: S(C) = Cd ( mod n) Tất cả những bước trên áp dụng cho cả mã hóa và chữ ký số. Để tạo một chữ ký kỹ thuật số người ký chữ số đó áp dụng khóa bí mật của mình vào thông báo được ký, thay vì cho một văn bản mật mã. Để xác minh một chữ ký kỹ thuật số khóa công khai RSA của người ký chữ ký đó được áp dụng vào nó, thay cho một thông báo được mã hóa. 3. Tính đúng đắn của RSA. Ta có các công thức : P(M) =Me ( mod n) Và S(C) = Cd ( mod n) Định nghĩa các phép biến đổi nghịch đảo Zn thoả các điều kiện trên M = SA(PA(M)) M= PA(SA(M)) Từ các phương trình: P(M) =Me ( mod n) S(C) = Cd ( mod n) Ta có bất kỳ M Zn thì P(S(M)) =S(P(M))= Med(mod n). Vì e và d là các nghịch đảo nhân môđun Þ(n) = (p-1)(q-1), ed = 1+ k(p-1)(q-1) với một số nguyên k. Nếu M0 (mod p), ta có: Med M (Mp-1)k(q-1) (mod p) M (1)k(q-1) (mod p) M (mod p) Ngoài ra, Med M (mod p) nếu M0 (mod p) Med M (mod p) với M. Tương tự, ta có: Med M (mod q) với M. Theo định lý phần dư Trung Quốc, ta có: Med M (mod n) với M. 4. Tính bảo mật. Tính bảo mật của hệ mã hóa mật mã công khai RSA phần lớn dựa vào việc lấy thừa số các số nguyên lớn. Kẻ xâm nhập có thể lấy thừa số môđun n trong một khóa công khai thì kẻ xâm nhập đó có thể suy ra khoá bí mật từ khoá công khai này rồi lấy thừa số các số nguyên lớn dễ dàng thì việc bẻ khóa hệ mật mã công khai RSA cũng dễ dàng nhưng nếu lấy thừa số các số nguyên lớn khó khăn thì việc bẻ khóa cũng gặp rất nhiều khó khăn. Cho đến nay, người ta vẫn chưa tìm ra phương pháp nào dễ dàng hơn trong việc bẻ mật mã khóa công khai RSA hơn là lấy thừa số môđun n. Với một số nguyên n, ta muốn lấy thừa số, có nghĩa là, phân tích thành một tích các số nguyên tố và với phép thử tính nguyên sẽ cho ta biết n là hợp số nhưng thông thường không cho ta biết các thừa số nguyên tố của n. Đối với việc lấy thừa số nguyên tố khó hơn rất nhiều lần so với việc đơn giản xác định n là số nguyên tố hay là hợp số. Bằng cách chọn ngẫu nhiên và nhân hai số nguyên tố 100 chữ số với nhau ta có thể tạo ra một khóa công khai không thể nào phá được trong một thời gian khả thi với những công nghệ hiện hành. Nhưng để có thể có được tính bảo mật cao bằng hệ mã hoá mật mã công khai RSA ta cần làm việc với các số nguyên tố có chiều dài 100 – 200 chữ số, vì việc lấy thừa số các số nguyên nhỏ hơn là không thực tế. Do đó ta có thể tìm ra các số nguyên tố lớn một cách hiệu quả để tạo ra khóa có chiều dài cần thiết. Hình 7: Hệ thống mã hoá mật mã dùng khóa công khai. Giải thuật RSA sử dụng hai khoá khác nhau để mã hoá và giải mã dữ liệu. 5. Các ví dụ về giải thuật RSA. Ví dụ 1. Ta chọn: P = 61 <- số nguyên tố đầu tiên (bị hủy đi sau khi tính toán E và D) Q = 53 <- số nguyên tố thứ hai (bị hủy đi sau khi tính toán E và D) PQ = 3233 <- môđun E = 17 <- số mũ chung D = 2753 <- số mũ riêng (được giữ bí mật) Khoá công khai của bạn là: (E, PQ). Khoá bí mật của bạn là: D. Hàm để mã hoá là: encrypt(T) = (T^E) mod PQ = (T^17) mod 3233 Hàm để giải mã là: decrypt(C) = (C^D) mod PQ = (C^2753) mod 3233 Ta mã hoá một văn bản có giá trị là 123, ta làm như sau: encrypt(123) = (123^17) mod 3233 = 337587917446653715596592958817679803 mod 3233 = 855 Ta muốn mã hóa một văn bản đã mã hoá có giá trị 855, ta làm như sau: decrypt(855) = (855^2753) mod 3233 = 123 Cách để người ta tính toán giá trị 855^2753 mod 3233 người ta làm như sau: Phân tích ra thành thừa số 2, ta có: 2753 = 101011000001 cơ số 2 Do đó ta có: 2753 = 1 + 2^6 + 2^7 + 2^9 + 2^11 = 1 + 64 + 128 + 512 + 2048 Ta đưa đến bảng lũy thừa của 855: 855^1 = 855 (mod 3233) 855^2 = 367 (mod 3233) 855^4 = 367^2 (mod 3233) = 2136 (mod 3233) 855^8 = 2136^2 (mod 3233) = 733 (mod 3233) 855^16 = 733^2 (mod 3233) = 611 (mod 3233) 855^32 = 611^2 (mod 3233) = 1526 (mod 3233) 855^64 = 1526^2 (mod 3233) = 916 (mod 3233) 855^128 = 916^2 (mod 3233) = 1709 (mod 3233) 855^256 = 1709^2 (mod 3233) = 1282 (mod 3233) 855^512 = 1282^2 (mod 3233) = 1160 (mod 3233) 855^1024 = 1160^2 (mod 3233) = 672 (mod 3233) 855^2048 = 672^2 (mod 3233) = 2197 (mod 3233) Đưa về theo yêu cầu trên ta có: 855^2753 (mod 3233) = 855^(1 + 64 + 128 + 512 + 2048) (mod 3233) = 855^1 * 855^64 * 855^128 * 855^512 * 855^2048 (mod 3233) = 855 * 916 * 1709 * 1160 * 2197 (mod 3233) = 794 * 1709 * 1160 * 2197 (mod 3233) = 2319 * 1160 * 2197 (mod 3233) = 184 * 2197 (mod 3233) = 123 (mod 3233) = 123 Tính theo máy tính bằng chương trình Calculator ta có: 855^ 2753 b. Ví dụ 2 : Ta chọn p=11, q=3. n = pq = 11.3 = 33 phi = (p-1)(q-1) = 10.2 = 20 e= 3 gcd(e, p-1) = gcd(3, 10) = 1 (vì 3 và 10 không có ước số chung lớn nhất nào khác ngoài 1) gcd(e, q-1) = gcd(3, 2) = 1 ( tương tự như trên) Vì thế, gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1 Tìm d sao cho ed ≡ 1 (mod phi)Giả sử ta tính toán d=e^-1mod phi = 3^-1 mod 20Ta tìm được d với phi chia cho (ed-1) hay 20/(3d -1) Chọn d= ( 1, 2, 3…), lấy d= 7. Ta có : ed-1 = 3.7 - 1 = 20 Vậy khoá công khai là: (n, e) = (33, 3) khóa bí mật là: (n, d) = (33, 7). Bây giờ ta sẽ mã hoá một thông báo m =7. Ta có: c = m^e mod n = 7^3 mod 33 = 343 mod 33 = 13 Lúc này thông báo đã được mã hóa là: c= 13. Và để kiểm tra giải mã, ta tính toán: m' = c^d mod n = 13^7 mod 33 = 7. Chú ý rằng ở đây ta không áp dụng tính với số 13 để có số 7 mà ta tính toán theo cách sau: m' = 13^7 mod 33 = 13^(3+3+1) mod 33 = 13^3.13^3.13 mod 33= (13^3 mod 33).(13^3 mod 33).(13 mod 33) mod 33= (2197 mod 33).(2197 mod 33).(13 mod 33) mod 33= 19.19.13 mod 33 = 4693 mod 33 =7 Nếu ta tính toán c từ m có giá trị ( 0, 32) ta có: m 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 c 0 1 8 27 31 26 18 13 17 3 10 11 12 19 5 9 4 m 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 c 29 24 28 14 21 22 23 30 16 20 15 7 2 6 25 32 Nhưng theo hệ thống Unicode ta sẽ bỏ đi 0 và 1 không còn bí mật nữa mà nó công khai vì khi ta đã mã hoá rồi mà nó vẫn còn nguyên như cũ. Do đó phải loại bỏ nó đi và ta chọn số khác. Nếu ta muốn sử dụng hệ thống bảo mật này ta cần chọn A=2, B=3, ..., Z=27. Chẳng hạn như ta muốn chọn thông báo cần mã hoá có tên là: "HELLOWORLD" và được thể hiện dưới dạng số nguyên m1, m2… Ta có: {9, 6, 13, 13, 16, 24, 16, 19, 13, 5} Và ta có thông báo mã hoá: {3, 18, 19, 19, 4, 30, 4, 28, 19, 26} Chú ý rằng: Cách mã hoá trên gần giống với Ceasar nhưng không phải vì ta sử dụng giải thuật RSA. c. Ví dụ 3: Cho một thông báo sau: ATTACKxATxSEVEN = ATT ACK XAT XSE VEN Ta chia thông báo kia theo khối gồm 3 ký tự, dựa trên nền gồm 26 ký tự: A=0, B=1, C=2, ..., Z=25 ATT = 0 x 26^2 + 19 x 26^1 + 19 = 513 ACK = 0 x 26^2 + 2 x 26^1 + 10 = 62 XAT = 23 x 26^2 + 0 x 26^1 + 19 = 15567 XSE = 23 x 26^2 + 18 x 26^1 + 4 = 16020 VEN = 21 x 26^2 + 4 x 26^1 + 13 = 14313 Với ví dụ trên ta không phải lo lắng về các con số và các ký tự chấm câu hay những nhóm như AAA hay AAB. Trong hệ thống mã hoá này giá trị lớn nhất của cụm ZZZ là 26^3-1 = 17575 vì thế ta phải yêu cầu một số môđun n lớn hơn số này. Ta “sinh” ra cặp khoá số nguyên tố p=137 và q=131 n = pq = 137.131 = 17947phi = (p-1)(q-1) = 136.130 = 17680 chọn e = 3Kiểm tra gcd(e, p-1) = gcd(3, 136) = 1, kiểm tra gcd(e, q-1) = gcd(3, 130) = 1, cả hai đều phù hợp à chọn. Ta tính toán: d = e^-1 mod phi = 3^-1 mod 17680 = 11787. Lúc này cặp khóa như sau: khóa công khai là (n, e) = (17947, 3) và khoá bí mật là: (n, d) = (17947, 11787). Hàm mã hoá RSA. unsigned long RSA_encrypt(char *source, unsigned long source_size, char *result, unsigned long result_size, char *pubkey_content, unsigned long pubkey_content_size) { if(!RSA_load_public_certificate_from_buffer(pubkey, pubkey_content, pubkey_content_size)) goto err; chiper_block_length_byte =