Báo cáo Hệ mã hóa công khai RSA

yên chỉ chia chẵn được cho 1 và cho chính nó mà thôi. Ví dụ : 2, 3, 5, 7, 11, 13, 17, 23... 2- Khái niệm nguyên tố cùng nhau (relatively prime or coprime)Với hai số nguyên dương a và b . Ta ký hiệu GCD (a,b) : Ước chung lớn nhất của a và b ( Greatest Common Divisor)Để đơn giản ta ký hiệu GCD(a,b) =(a,b)Ví dụ : (4,6)=2(5,6)=1Hai số a và b gọi là nguyên tố cùng nhau khi (a,b)=1Ví dụ : 9 và 10 nguyên tố cùng nhau vì (9,10)=1 3-Khái niệm moduloVới m là một số nguyên dương .Ta nói hai số nguyên a va b là đồng dư với nhau modulo m nếu m chia hết hiệu a-b ( Viết là m|(a-b) )Ký hiệu a ≡ b ( mod m) Như vậy a ≡ b (mod m ) khi và chỉ khi tồn tại số nguyên k sao cho a = b +km Ví dụ : 13 ≡ 3 ( mod 10 ) vì 13= 3 + 1*10 4-Phi – Hàm EULER Định nghĩa : Phi – Hàm Euler Φ(n) có giá trị tại n bằng số các số không vượt quá n và nguyên tố cùng nhau với nVí dụ : Φ(5) = 4 , Φ(6) = 2 ,Φ(10) = 4 5-Một số định lý cơ bảnĐịnh lý Euler : nếu m là số nguyên dương và P nguyên tố cùng nhau với m thì P^Φ(m) ≡ 1 (mod m )Vậy nếu m và p nguyên tố cùng nhau . Ta đặt s = Φ(m) thì P^s ≡ 1 (mod m) Suy ra với a= 1 + k*s Ta có : P^a ≡ P*(P^s)^k ≡ P*1^k(mod m) ≡ P (mod m)với e là số nguyên dương nguyên tố cùng nhau với s ,tức là (e,s)=1Khi đó tồn tại một nghịch đảo d của e modulo s tức là e*d ≡ 1 (mod s) e*d = 1 + k*sóĐặt E(P) ≡ C ≡ P^e(mod m)Đặt D(C) ≡ C^d (mod m)Ta thấy D(C) ≡ C^d ≡ P^e*d ≡ P^(1 + k*s )≡ P (mod m) Ví dụ :m = 10 , P = 9 ta có (10,9)=1s = Φ(10) = 4 e = 7 ta có (7,4) = 1 nghịch đảo của 7 modulo 4 la d = 3 vì 7*3 =1 + 5*4 Lúc đó ta cóE(P) ≡ C ≡ P^e ≡ 9 ^ 7 ≡ 4.782.969 ≡ 9 (mod 10) => C=9D(C) ≡ C^d ≡ 9^3 ≡ 729 ≡ 9(mod 10) Vậy D chính la hàm ngược của E đây là cơ sở cho việc xây dựng thuật toán RSA mà chúng ta sẽ bàn kỹ ở phần sau Tính Φ (m ) khi biết m . Chúng ta có định lý sau đây :Giả sử m = p1^a1*p2^a2*… *pk^ak .Khi đó Φ(m) =( p1^a1 – p1^(a1-1) )* … * (pk^ak – pk^(ak-1) )Ví dụ : m= 10 Ta phân tích 10 =2*5=> Φ(10) =( 2^1 – 2^0) *(5^1 – 5^0) = 1*4 = 4 IV. Hệ mã hóa RSA: 1. Giới thiệu RSA được Rivest, Shamir và Adleman phát triển, là một thuận toán mật mã hóa khóa công khai. Nó đánh dấu một sự tiến hóa vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công khai. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn. Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT). Tên của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả. Trước đó, vào năm 1973, Clifford Cocks, một nhà toán học người Anh làm việc tại GCHQ, đã mô tả một thuật toán tương tự. Với khả năng tính toán tại thời điểm đó thì thuật toán này không khả thi và chưa bao giờ được thực nghiệm. Tuy nhiên, phát minh này chỉ được công bố vào năm 1997 vì được xếp vào loại tuyệt mật. RSA là một thí dụ điển hình về một đề tài toán học trừu tượng lại có thể áp dụng thực tiễn vào đời sống thường nhật . Khi nghiên cứu về các số nguyên tố, ít có ai nghĩ rằng khái niệm số nguyên tố lại có thể hữu dụng vào lãnh vực truyền thông.  Cách tạo khóa: Chúng ta cần tạo ra một cặp khóa lập mã và giải mã theo phương pháp sau: Chọn 2 số nguyên tố lớn và với , lựa chọn ngẫu nhiên và độc lập. Tính: . Tính: giá trị hàm số Ơle . Chọn một số tự nhiên e sao cho và là số nguyên tố cùng nhau với . Tính: d sao cho . Một số lưu ý: Các số nguyên tố thường được chọn bằng phương pháp thử xác suất. Các bước 4 và 5 có thể được thực hiện bằng giải thuật Euclid mở rộng (xem thêm: số học môđun). Bước 5 có thể viết cách khác: Tìm số tự nhiên sao cho cũng là số tự nhiên. Khi đó sử dụng giá trị . Từ bước 3, PKCS#1 v2.1 sử dụng thay cho ). Khóa công khai bao gồm: n, môđun, và e, số mũ công khai (cũng gọi là số mũ mã hóa). Khóa bí mật bao gồm: n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và d, số mũ bí mật (cũng gọi là số mũ giải mã). Một dạng khác của khóa bí mật bao gồm: p and q, hai số nguyên tố chọn ban đầu, d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1), (1/q) mod p (thường được gọi là iqmp) Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem - CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa. *Chuyển đổi thông tin: Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi thông tin (chuyển đổi từ M sang m) sao cho không có giá trị nào của M tạo ra văn bản mã không an toàn. Nếu không có quá trình này, RSA sẽ gặp phải một số vấn đề sau: Nếu m = 0 hoặc m = 1 sẽ tạo ra các bản mã có giá trị là 0 và 1 tương ứng Khi mã hóa với số mũ nhỏ (chẳng hạn e = 3) và m cũng có giá trị nhỏ, giá trị me cũng nhận giá trị nhỏ (so với n). Như vậy phép môđun không có tác dụng và có thể dễ dàng tìm được m bằng cách khai căn bậc e của c (bỏ qua môđun). RSA là phương pháp mã hóa xác định (không có thành phần ngẫu nhiên) nên kẻ tấn công có thể thực hiện tấn công lựa chọn thông tin bằng cách tạo ra một bảng tra giữa thông tin và bản mã. Khi gặp một bản mã, kẻ tấn công sử dụng bảng tra để tìm ra thông tin tương ứng. Trên thực tế, ta thường gặp 2 vấn đề đầu khi gửi các bản tin ASCII ngắn với m là nhóm vài ký tự ASCII. Một đoạn tin chỉ có 1 ký tự NULL sẽ được gán giá trị m = 0 và cho ra bản mã là 0 bất kể giá trị của e và N. Tương tự, một ký tự ASCII khác, SOH, có giá trị 1 sẽ luôn cho ra bản mã là 1. Với các hệ thống dùng giá trị e nhỏ thì tất cả ký tự ASCII đều cho kết quả mã hóa không an toàn vì giá trị lớn nhất của m chỉ là 255 và 2553 nhỏ hơn giá trị n chấp nhận được. Những bản mã này sẽ dễ dàng bị phá mã. Để tránh gặp phải những vấn đề trên, RSA trên thực tế thường bao gồm một hình thức chuyển đổi ngẫu nhiên hóa m trước khi mã hóa. Quá trình chuyển đổi này phải đảm bảo rằng m không rơi vào các giá trị không an toàn. Sau khi chuyển đổi, mỗi thông tin khi mã hóa sẽ cho ra một trong số khả năng trong tập hợp bản mã. Điều này làm giảm tính khả thi của phương pháp tấn công lựa chọn thông tin (một thông tin sẽ có thể tương ứng với nhiều bản mã tuỳ thuộc vào cách chuyển đổi). Một số tiêu chuẩn, chẳng hạn như PKCS, đã được thiết kế để chuyển đổi thông tin trước khi mã hóa bằng RSA. Các phương pháp chuyển đổi này bổ sung thêm bít vào M. Các phương pháp chuyển đổi cần được thiết kế cẩn thận để tránh những dạng tấn công phức tạp tận dụng khả năng biết trước được cấu trúc của thông tin. Phiên bản ban đầu của PKCS dùng một phương pháp đặc ứng (ad-hoc) mà về sau được biết là không an toàn trước tấn công lựa chọn thông tin thích ứng (adaptive chosen ciphertext attack). Các phương pháp chuyển đổi hiện đại sử dụng các kỹ thuật như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding - OAEP) để chống lại tấn công dạng này. Tiêu chuẩn PKCS còn được bổ sung các tính năng khác để đảm bảo an toàn cho chữ ký RSA (Probabilistic Signature Scheme for RSA - RSA-PSS). Mã hóa Giả sử có đoạn thông tin M cần gửi. Đầu tiên chuyển M thành một số m<n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Lúc này ta có m và biết n cũng như e của người nhận. Ta sẽ tính c là bản mã hóa của m theo công thức: Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân) Cuối cùng Ta gửi c cho đối tác. Giải mã Khi đối tác nhận c từ ta. Đối tác sử dụng khóa bí mật d tìm được m từ c theo công thức sau: Biết m, đối tác tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có . Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên: và Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có: . hay: . Sơ đồ của quá trình Tính bảo mật Độ an toàn của hệ thống RSA dựa trên 2 vấn đề của toán học: bài toán phân tích ra thừa số nguyên tố các số nguyên lớn và bài toán RSA. Nếu 2 bài toán trên là khó (không tìm được thuật toán hiệu quả để giải chúng) thì không thể thực hiện được việc phá mã toàn bộ đối với RSA. Bài toán RSA là bài toán tính căn bậc e môđun n (với n là hợp số): tìm số m sao cho me=c mod n, trong đó (e, n) chính là khóa công khai và c là bản mã. Hiện nay phương pháp triển vọng nhất giải bài toán này là phân tích n ra thừa số nguyên tố. Khi thực hiện được điều này, kẻ tấn công sẽ tìm ra số mũ bí mật d từ khóa công khai và có thể giải mã theo đúng quy trình của thuật toán. Nếu kẻ tấn công tìm được 2 số nguyên tố p và q sao cho: n = pq thì có thể dễ dàng tìm được giá trị (p-1)(q-1) và qua đó xác định d từ e. Chưa có một phương pháp nào được tìm ra trên máy tính để giải bài toán này trong thời gian đa thức (polynomial-time). Tuy nhiên người ta cũng chưa chứng minh được điều ngược lại (sự không tồn tại của thuật toán). Xem thêm phân tích ra thừa số nguyên tố về vấn đề này. Tại thời điểm năm 2005, số lớn nhất có thể được phân tích ra thừa số nguyên tố có độ dài 663 bít với phương pháp phân tán trong khi khóa của RSA có độ dài từ 1024 tới 2048 bít. Một số chuyên gia cho rằng khóa 1024 bít có thể sớm bị phá vỡ (cũng có nhiều người phản đối việc này). Với khóa 4096 bít thì hầu như không có khả năng bị phá vỡ trong tương lai gần. Do đó, người ta thường cho rằng RSA đảm bảo an toàn với điều kiện n được chọn đủ lớn. Nếu n có độ dài 256 bít hoặc ngắn hơn, nó có thể bị phân tích trong vài giờ với máy tính cá nhân dùng các phần mềm có sẵn. Nếu n có độ dài 512 bít, nó có thể bị phân tích bởi vài trăm máy tính tại thời điểm năm 1999. Một thiết bị lý thuyết có tên là TWIRL do Shamir và Tromer mô tả năm 2003 đã đặt ra câu hỏi về độ an toàn của khóa 1024 bít. Vì vậy hiện nay người ta khuyến cáo sử dụng khóa có độ dài tối thiểu 2048 bít. Năm 1993, Peter Shor công bố thuật toán Shor chỉ ra rằng: máy tính lượng tử (trên lý thuyết) có thể giải bài toán phân tích ra thừa số trong thời gian đa thức. Tuy nhiên, máy tính lượng tử vẫn chưa thể phát triển được tới mức độ này trong nhiều năm nữa. Quá trình tạo khóa Việc tìm ra 2 số nguyên tố đủ lớn p và q thường được thực hiện bằng cách thử xác suất các số ngẫu nhiên có độ lớn phù hợp (dùng phép kiểm tra nguyên tố cho phép loại bỏ hầu hết các hợp số). p và q còn cần được chọn không quá gần nhau để phòng trường hợp phân tích n bằng phương pháp phân tích Fermat. Ngoài ra, nếu p-1 hoặc q-1 có thừa số nguyên tố nhỏ thì n cũng có thể dễ dàng bị phân tích và vì thế p và q cũng cần được thử để tránh khả năng này. Bên cạnh đó, cần tránh sử dụng các phương pháp tìm số ngẫu nhiên mà kẻ tấn công có thể lợi dụng để biết thêm thông tin về việc lựa chọn (cần dùng các bộ tạo số ngẫu nhiên tốt). Yêu cầu ở đây là các số được lựa chọn cần đồng thời ngẫu nhiên và không dự đoán được. Đây là các yêu cầu khác nhau: một số có thể được lựa chọn ngẫu nhiên (không có kiểu mẫu trong kết quả) nhưng nếu có thể dự đoán được dù chỉ một phần thì an ninh của thuật toán cũng không được đảm bảo. Một ví dụ là bảng các số ngẫu nhiên do tập đoàn Rand xuất bản vào những năm 1950 có thể rất thực sự ngẫu nhiên nhưng kẻ tấn công cũng có bảng này. Nếu kẻ tấn công đoán được một nửa chữ số của p hay q thì chúng có thể dễ dàng tìm ra nửa còn lại (theo nghiên cứu của Donald Coppersmith vào năm 1997) Một điểm nữa cần nhấn mạnh là khóa bí mật d phải đủ lớn. Năm 1990, Wiener chỉ ra rằng nếu giá trị của p nằm trong khoảng q và 2q (khá phổ biến) và d < n1/4/3 thì có thể tìm ra được d từ n và e. Mặc dù e đã từng có giá trị là 3 nhưng hiện nay các số mũ nhỏ không còn được sử dụng do có thể tạo nên những lỗ hổng (đã đề cập ở phần chuyển đổi văn bản rõ). Giá trị thường dùng hiện nay là 65537 vì được xem là đủ lớn và cũng không quá lớn ảnh hưởng tới việc thực hiện hàm mũ. Tốc độ RSA có tốc độ thực hiện chậm hơn đáng kể so với DES và các thuật toán mã hóa đối xứng khác. Trên thực tế, Bob sử dụng một thuật toán mã hóa đối xứng nào đó để mã hóa văn bản cần gửi và chỉ sử dụng RSA để mã hóa khóa để giải mã (thông thường khóa ngắn hơn nhiều so với văn bản). Phương thức này cũng tạo ra những vấn đề an ninh mới. Một ví dụ là cần phải tạo ra khóa đối xứng thật sự ngẫu nhiên. Nếu không, kẻ tấn công (thường ký hiệu là Eve) sẽ bỏ qua RSA và tập trung vào việc đoán khóa đối xứng. 8. Các dạng tấn công a. Phân phối khóa Cũng giống như các thuật toán mã hóa khác, cách thức phân phối khóa công khai là một trong những yếu tố quyết định đối với độ an toàn của RSA. Quá trình phân phối khóa cần chống lại được tấn công đứng giữa (man-in-the-middle attack). Giả sử kẻ xấu(C) có thể gửi cho Người gửi thông tin(A) một khóa bất kỳ và khiến (A) tin rằng đó là khóa (công khai) của Đối tác(B). Đồng thời (C) có khả năng đọc được thông tin trao đổi giữa (A) và (B). Khi đó, (C) sẽ gửi cho (A) khóa công khai của chính mình (mà (A) nghĩ rằng đó là khóa của (B)). Sau đó, (C) đọc tất cả văn bản mã hóa do (A) gửi, giải mã với khóa bí mật của mình, giữ 1 bản copy đồng thời mã hóa bằng khóa công khai của (B) và gửi cho (B). Về nguyên tắc, cả (A) và (B) đều không phát hiện ra sự can thiệp của người thứ ba. Các phương pháp chống lại dạng tấn công này thường dựa trên các chứng thực khóa công khai (digital certificate) hoặc các thành phần của hạ tầng khóa công khai (public key infrastructure - PKI). b. Tấn công dựa trên thời gian Vào năm 1995, Paul Kocher mô tả một dạng tấn công mới lên RSA: nếu kẻ tấn công nắm đủ thông tin về phần cứng thực hiện mã hóa và xác định được thời gian giải mã đối với một số bản mã lựa chọn thì có thể nhanh chóng tìm ra khóa d. Dạng tấn công này có thể áp dụng đối với hệ thống chữ ký điện tử sử dụng RSA. Năm 2003, Dan Boneh và David Brumley chứng minh một dạng tấn công thực tế hơn: phân tích thừa số RSA dùng mạng máy tính (Máy chủ web dùng SSL). Tấn công đã khai thác thông tin rò rỉ của việc tối ưu hóa định lý số dư Trung quốc mà nhiều ứng dụng đã thực hiện. Để chống lại tấn công dựa trên thời gian là đảm bảo quá trình giải mã luôn diễn ra trong thời gian không đổi bất kể văn bản mã. Tuy nhiên, cách này có thể làm giảm hiệu suất tính toán. Thay vào đó, hầu hết các ứng dụng RSA sử dụng một kỹ thuật gọi là che mắt. Kỹ thuật này dựa trên tính nhân của RSA: thay vì tính cd mod n, Alice đầu tiên chọn một số ngẫu nhiên r và tính (rec)d mod n. Kết quả của phép tính này là rm mod n và tác động của r sẽ được loại bỏ bằng cách nhân kết quả với nghịch đảo của r. Đỗi với mỗi văn bản mã, người ta chọn một giá trị của r. Vì vậy, thời gian giải mã sẽ không còn phụ thuộc vào giá trị của văn bản mã. c. Tấn công bằng phương pháp lựa chọn thích nghi bản mã Năm 1981, Daniel Bleichenbacher mô tả dạng tấn công lựa chọn thích nghi bản mã (adaptive chosen ciphertext attack) đầu tiên có thể thực hiện trên thực tế đối với một văn bản mã hóa bằng RSA. Văn bản này được mã hóa dựa trên tiêu chuẩn PKCS #1 v1, một tiêu chuẩn chuyển đổi bản rõ có khả năng kiểm tra tính hợp lệ của văn bản sau khi giải mã. Do những khiếm khuyết của PKCS #1, Bleichenbacher có thể thực hiện một tấn công lên bản RSA dùng cho giao thức SSL (tìm được khóa phiên). Do phát hiện này, các mô hình chuyển đổi an toàn hơn như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding) được khuyến cáo sử dụng. Đồng thời phòng nghiên cứu của RSA cũng đưa ra phiên bản mới của PKCS #1 có khả năng chống lại dạng tấn công nói trên. V. chữ kí điện tử: Hệ mã RSA có tính an toàn rất cao . Nhưng nhược điểm lớn là tốc độ mã hóa chậm (nhất là so với các hệ mã đối xứng có cùng độ an toàn ) . Bởi vậy nó chỉ được sử dụng với các văn bản ngắn , và thường dùng trong giao thức xác nhận chủ thể(chữ kí điện tử)Chữ kí điện tử đảm bảo khi người nhận có được mật thư thì biết chắc chắn ai là tác giả bức thư đó . Và cũng đảm bảo việc không ai có thể mạo danh người khác để gửi thư. Chữ kí điện tử và chữ kí tay có chung đặt điểm là rất khó xảy ra trường hợp trùng. Để làm được điều đó , khi anh U muốn gửi bức thư P cho anh V . Đầu tiên anh U dùng khóa lập mã Ev ( được công khai của anh V ) để mã hóa P thu được Ev ( P ) . Sau đó dùng khóa giải mã của mình là Du ( bí mật ) để tính Du (Ev ( P )) = C và gửi đi . Sau khi nhận được mật thư C , anh V sẽ dùng khóa lập mã của anh U là Eu ( công khai ) đế tính Eu (C) = Eu (Du (Ev ( P ))) = Ev ( P ) ( do Eu là hàm ngược của Du ) Cuối cùng dùng khóa giải mã bí mật Dv để tính ra Dv (Ev ( P )) = P chính là bức thư ban đầu .Rõ ràng với cách này chúng ta chỉ có thể áp dụng với những văn bản ngắn ,còn khi văn bản dài chúng ta phải áp dụng một phương pháp biến thể từ phương pháp trên , đó là sử dụng hàm băm . Đó là một hàm đựơc công khai trên toàn hệ thống . Khi cần gửi văn bản , người ta sẽ gửi kèm theo bản giá trị băm của văn bản , sau khi nhận được người ta sẽ băm văn bản lại lần nữa và so sánh với giá trị băm của bên gửi , nếu trùng khớp thì có thể khẳng định văn bản đã không bị thay đổi trên đường đi … Mô hình chữ kí điện tử VI. Chương trình hiện thực thuật toán Mã hóa RSA: 2 tác vụ chính của chương trình là tính, tạo ra cặp khóa của hệ RSA, và thực hiện mã hóa một đoạn văn bản ngắn theo phương thức này: I.Tạo cặp khóa (e,n) và (d,n): Các số liệu cấn phát sinh là p,q,e: Các hàm cần xây dựng: Hàm kiểm tra số nguyên tố: public bool kt_SNT(int number) { if (number == 1 || number == 2) return true; else { int tam = (int)Math.Sqrt(number); for (int i = 2; i <= tam; i++) { if (number % i == 0) return false; } } return true; } Hàm tìm ước số chung lớn nhất: public int USCLN(int a, int b) { if (b == 0) return a; else return USCLN(b, a % b); } Hàm kiểm tra 2 số có phải là nguyên tố cùng nhau không: public bool kt_NTCN(int a, int b) { if (USCLN(a, b) == 1) return true; else return false; } 3 hàm trên sử dụng cho việc phát sinh các số p,q,e theo đúng Thuật toán mã hóa RSA: Hảm tính d,n theo p,q,e: public void tinhkey() { n = p * q; //// tim d int i = 1; int temp; do { temp = 1 + i * delta; d = (1 + i * delta) / ei; i++; } while (!(d * ei == temp)); } II. Mã hóa một đoạn văn bản: Việc mã hóa một đoạn text ngắn sẽ được thực hiện như sau: Giã sử ta có đoạn text ABCD Trước tiên ta thực hiện chuyển đoạn text về dạng số theo nguyên tắt sau: Ta quy định các kí tự sẽ tương ứng với các số như sau (ta chỉ xét kí tự thường) a 01 n 14 b 02 o 15 c 03 p 16 d 04 q 17 e 05 r 18 f 06 s 19 g 07 t 20 h 08 u 21 i 09 v 22 J 10 w 23 k 11 x 24 l 12 y 25 m 13 z 26 space 27 Kết quả: A B C D sẻ chuyển thành : 01 02 03 04: Sau khi chuyển các chữ cái trong văn bản thành các chữ số tiếp theo nhóm chúng lại thành từng khối như sau :0102 0304 ( lưu ý là khi khối cuối cùng chỉ có một chữ cái ta thêm vào một chữ cái khác sao cho không gây sự hiểu lầm , thường ta thêm vào chữ kí tự space) Và bây giờ ta tiến hành mã hóa theo từng khối: Để mã hóa từng khối P ta thực hiện C= (P ^e) mod n Giải mã: P = (C^d) mod n Ví dụ ta có p =61, q = 53, e =17 tính được, n = 3233, d = 2753, Trong đó giá trị trung gian đề tính d Φ(n) = 3120. Lưu ý: chọn e và khối tin P Ta phải chọn e sao cho 2 ^ e > n . ( => P^e > n với mọi P ) . Vì Nếu P^e n thì :Khi giải mã một khối C : ta có D(C) ≡ P(mod n) ≡ P1 ( mod n) ( với P1 < n < P )Ta không tìm được giá trị P ban đầu Ví dụ: Ta thực hiện mã hóa: “aw“ Trước tiên ta thực hiện chuyển aw -> 0123: Sau đó mã hóa nó theo công thức đã trình bày ở trên ta được: (0123 ^ 17) mod 3233 = 855 Vậy 855 là thông tin dạng mã, để đọc được ta cần gải mã nó: (855 ^ 2735) mod 3233 = 123: Khi nhận được thông tin góc dạng số ta đưa nó về đúng format: 123 -> 0123 Sau đó chuyển về dạng kí tự: 0123 -> aw Ở đây chúng ta mã hóa đoạn văn bản theo từng khối, Văn bản dược chia nhỏ và mã hóa theo thứ tự, Khi giải mã ta cũng thực hiện gải mã theo từng khối và đúng thứ tự. Một điểm cần lưu ý: trong quá trình tính toán ta gặp (855^2735) mod 3233 855^2735 là một số rất lớn: 855^2735 = 50432888958416068734422899127394466631453878360035509315554967564501 05562861208255997874424542811005438349865428933638 493024645144150785 17209179665478263530709963803538732650089668607477 182974582295034295 04079035818459409563779385865989368838083602840132 509768620766977396 67533250542826093475735137988063256482639334453092 594385562429233017 51977190016924916912809150596019178760171349725439 279215696701789902 13430714646897127961027718137839458696772898693423 652403116932170892 69617643726521315665833158712459759803042503144006 837883246101784830 71758547454725206968892599589254436670143220546954 317400228550092386 36942444855973333063051607385302863219302913503745 471946757776713579 54965202919790505781532871558392070303159585937493 663283548602090830 63550704455658896319318011934122017826923344101330 116480696334024075 04695258866987658669006224024102088466507530263953 870526631933584734 81094876156227126037327597360375237388364148088948 438096157757045380 08107946980066734877795883758289985132793070353355 127509043994817897 90548993381217329458535447413268056981087263348285 463816885048824346 58897839333466254454006619645218766694795528023088 412465948239275105 77049113329025684306505229256142730389832089007051 511055250618994171 23177795157979429711795475296301837843862913977877 661298207389072796 76720235011399271581964273076407418989190486860748 124549315795374377 12441601438765069145868196402276027766869530903951 314968319097324505 45234594477256587887692693353918692354818518542420 923064996406822184 49011913571088542442852112077371223831105455431265 307394075927890822 60604317113339575226603445164525976316184277459043 201913452893299321 61307440532227470572894812143586831978415597276496 357090901215131304 15756920979851832104115596935784883366531595132734 467524394087576977 78908490126915322842080949630792972471304422194243 906590308142893930 29158483087368745078977086921845296741146321155667 865528338164806795 45594189100695091965899085456798072392370846302553 545686919235546299 57157358790622745861957217211107882865756385970941 907763205097832395 71346411902500470208485604082175094910771655311765 297473803176765820 58767314028891032883431850884472116442719390374041 315564986995913736 51621084511374022433518599576657753969362812542539 006855262454561419 25880943740212888666974410972184534221817198089911 953707545542033911 96453936646179296816534265223463993674233097018353 390462367769367038 05342644821735823842192515904381485247388968642443 703186654199615377 91396964900303958760654915244945043600135939277133 952101251928572092 59788751160195962961569027116431894637342650023631 004555718003693586 05526491000090724518378668956441716490727835628100 970854524135469660 84481161338780654854515176167308605108065782936524 108723263667228054 00387941086434822675009077826512101372819583165313 969830908873174174 74535988684298559807185192215970046508106068445595 364808922494405427 66329674592308898484868435865479850511542844016462 352696931799377844 30217857019197098751629654665130278009966580052178 208139317232379013 23249468260920081998103768484716787498919369499791 482471634506093712 56541225019537951668976018550875993133677977939527 822273233375295802 63122665358948205566515289466369032083287680432390 611549350954590934 06676402258670848337605369986794102620470905715674 470565311124286290 73548884929899835609996360921411284977458614696040 287029670701478179 49024828290748416008368045866685507604619225209434 980471574526881813 18508591501948527635965034581536416565493160130613 304074344579651083 80304062240278898042825189094716292266898016684480 963645198090510905 79651307570379245958074479752371266761011473878742 144149154813591743 92799496956415653866883891715446305611805369728343 470219206348999531 91764016110392490439179803398975491765395923608511 807653184706473318 01578207412764787592739087492955716853665185912666 373831235945891267 87095838000224515094244575648744840868775308453955 217306366938917023 94037184780362774643171470855830491959895146776294 392143100245613061 11429937000557751339717282549110056008940898419671 319709118165542908 76109008324997831338240786961578492341986299168008 677495934077593066 02207814943807854996798945399364063685722697422361 858411425048372451 24465580270859179795591086523099756519838277952945 756996574245578688 38354442368572236813990212613637440821314784832035 636156113462870198 51423901842909741638620232051039712184983355286308 685184282634615027 44187358639504042281512399505995983653792227285847 422071677836679451 34363807086579774219853595393166279988789721695963 455346336497949221 13017661316207477266113107012321403713882270221723 233085472679533015 07998062253835458948024820043144726191596190526034 069061930939290724 10284948700167172969517703467909979440975063764929 6356