Cho mình hỏi?

Em không biết về RSA nhưng tìm thì có 1 số tài liệu RSA không biết chị có chưa.

Hệ Mã Hóa Rsa

I.GIỚI THIỆU VỀ MẬT MÃ

Số học – ngành khoa học lâu đời nhất của loài người , cho đến khoảng cuối những năm 70 thế kỷ trước vẫn chỉ được xem là một ngành lý thuyết thuần túy của toán học , vì hầu như không có những ứng dụng thực tế . Tuy nhiên cùng với sự phát triển của tin học , số học đã đóng một vai trò vô cung quan trong trong việc xây dựng ngành lý thuyết mật mã .Và hôm nay chúng ta sẽ bàn về hệ mã RSA ,được xây dựng trên cơ sở lý thuyết số hoc .

1- Mật mã bắt đầu từ đâu ?

Có thể nói mật mã đã có từ thời cổ đại . Như trong quân sự , để chuyển một bức mật thư
mà không sợ bị kẻ thù đọc được dù bức thư có thể bị mất , người ta đã mã hóa ( encode ) nó thành một bản các ký hiệu mà nếu không có khóa giải mã thì không thể nào biết nội dung ,và khi gửi đến bên nhận thì mật thư sẽ được giải mã (decode) theo một cách nào dó nhờ khóa giải mã. Hoặc trong thời đại ngày nay ,trong hoạt động thương mại ,đôi khi có những thông tin cần phải được giữ bí mật , người ta phải mã hóa nó lại …

2- Một số loại mật mã

Người ta cho rằng ,người đầu tiên áp dụng mật mã chính là nhà quân sự thiên tài của La Mã cổ đại , Julius Caesar . Mật mã này được dùng dĩ nhiên trong hoạt động quân sự.
Đó chính là mã Caesar ,hệ mã làm nền tảng choc các hệ mã phức tạp sau này.
Mã Caesar :
Trước tiên ta lập một bảng tương ứng giữa các chữ cái với các số như sau :


A B C D E F G H I J K L M
1 2 3 4 5 6 7 8 9 10 11 12 13

N O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25 26

Với bảng này để mã hóa một bức mật thư , ta cần một khóa lập mã k là 1 số nguyên bất kỳ , chẳng hạn ta cho k = 3 .Sau đó với bức thư ta chuyển nó thành một bản chỉ gồm các chữ số .Sau đó ta cộng thêm 3 vào mỗi chữ số để được bản mới gồm các chữ số . Cuối cùng chuyển bản chữ số mới này lại thành một văn bản chữ nhờ bảng tương ứng trên .
Khi nhận được văn bản ,ta giải mã bằng cách biến nó thành bản các chữ số ,sau đó trừ đi 3 với mỗi chữ số ,cuối cùng chuyển bản chữ số mới này thành bản chữ cái ,đó chính là văn bản ban đầu .
Lưu ý rằng khi các chữ số vượt quá bảng chữ số khi cộng thêm 3 , ta thay số đó bằng
thặng dư bé nhất modulo số phần tử của bảng chữ cái .
Như vậy Mã Caesar được thành lập theo công thức sau :
C ≡ P + 3 (mod 26 ) với P là chữ số trong văn bản nhận được ,C là chữ số trong văn bản mật được gửi đi .
Ví dụ :
Giả sử ta cần mã hóa một văn bản với nội dung sau :
DAY LA MA CAESAR
Trước hết ta chuyển bản trên thành bản chữ số , nhưng để đảm bảo tính an toàn ,
Tách văn bản thành từng nhóm 5 chữ cái như sau :
DAYLA MACAE SAR
Chuyển lại thành bản chữ số :
4 1 25 12 1 13 1 3 1 5 19 1 18
Chuyển bản chữ số này lại theo khóa k=3 (nếu chữ số nào vượt quá 26 thì lấy
phần dư của nó modulo 26 ) .Ta được bản chữ số sau :
7 4 2 15 4 17 4 6 4 8 22 4 21
Cuối cùng chuyển lại thành dạng chữ cái :
G D B O D Q D F D H V D U
Đây là văn bản mật có thể gửi đi .
Việc giải mã tiến hành tương tự khi biết dược khóa giải mã ,cũng chính là khóa lập mã
k = 3 ,ta áp dụng công thức C ≡ P + 3(mod 26 ) …
Dễ dàng nhận thấy rằng tính bảo mật của loại mã trên là không cao . Vì số khóa có
thể dùng để lập mã là không nhiều ( như với bảng chữ cái trên ta có tối đa 26 khóa )
Ngoài ra người ta còn phát triển thêm một số loai mã khác như : mã khối ,mã mũ với tính bảo mật cao hơn ,ngoài ra nó còn làm tiền đề xây dựng nên một hệ mã hoàn toàn mới,đó chính là các hệ mật mã khóa công khai như hệ mã RSA là chủ đề của bài thuyết trình này .

3- Các hệ mật mã khóa công khai

Với các loại mật mã được đề cập ở phần trên ,các khóa lập mã đều phải được giữ bí mật, vì
nếu có khóa lập mã ,người ta có thể tìm ra khóa giải mã trong thời gian tương đối ngắn .
Như vậy trong một hệ thống có nhiều cá thể cần trao đổi thông tin mật với nhau, số khóa mật mã chung cần được giữ bí mật là rất lớn,và như thế thì không thể đảm bảo an toàn .
Vì vậy người ta đã tìm cách xây dưng nên các hệ mã sao cho mỗi cá thể chỉ cần giữ bí mật khóa giải mã của riêng mình , còn khóa lập mã của mỗi người lại được thông báo công khai . Và dĩ nhiên không thể ( trong thời gian đủ dài ) tìm ra khóa giải mã từ khóa lập mã. Khi một cá thể bị lộ khóa giải mã của mình ,thì bí mật của các cá thể còn lại không hề bị ảnh hưởng .

Trước hết ta nói sơ về nguyên tắc của các hệ mã khóa công khai .
Giả sử trong hệ thống có n cá thể tham gia trao đổi thông tin mật . Mỗi cá thể chọn cho mình khóa lập mã k có công thức mã hóa Ek (Encode),công thức này được thông báo công khai, và một khóa giải mã của riêng mình ( cần được giữ bí mật ) có công thức Dk (Decode) .
Khi cá thể J cần gửi thư cho cá thể I,anh ta cần mã hóa bức thư đó theo công thức mã hóa Eki của cá thể I (đã được thông báo công khai ) , sau đó gửi đi . Khi cá thể I nhận được ,anh ta dùng khóa giải mã Dki của mình để giải mã bức thư . Như vậy khi bức thư này lọt ra ngoài thì vẫn không thể biết được nội dung vì khóa giải mã Dki chỉ có cá thể I biết mà thôi .

Với nguyên tắc trên , năm 1978 ,một hệ mã khóa công khai đầu tiên đã được đưa ra bởi Ronald Rivest , Adi Shamir và Leonard Adleman ( Sau này thường được gọi là hệ mã RSA
Chính là viết tắt của tên ba người Rivest-Shamir-Adleman)

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.



II.MỘT SỐ KHÁI NIỆM TOÁN HỌC CƠ BẢN

Trước hết, chúng ta sẽ nhắc lại những khái niệm toán học cơ bản cần thiết cho việc hiểu RSA.

Trong loạt bài này,
- con toán nhân được biểu thị bằng dấu hoa thị : *
Ví dụ:
3*2 có nghĩa là “3 nhân với 2” bằng 6

- lũy thừa hay “nâng lên mũ” được, biểu thị bằng dấu: ^
Ví dụ :
3^2 có nghĩa là “3 luỹ thừa 2”

1- Số nguyên tố (prime)

số nguyên tố là những số nguyê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)=1

Hai số a và b gọi là nguyên tố cùng nhau khi (a,b)=1
Ví dụ :
9 và 10 nguyên tố cùng nhau vì (9,10)=1

3-Khái niệm modulo

Vớ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 n
Ví 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)=1
Khi đó 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)=1
s = Φ(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=9
D(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

Làm sao để tính được Φ (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


Có những hàm số rất đơn giản, làm những việc rất đơn sơ, mà chúng ta biết rành rẽ ngọn ngành. Nhưng để tạo ra hàm ngược của nó, đi ngược từng bước, thì lại là một công việc vô vọng . Người ta thường gọi những hàm đó là những hàm số bẫy sập (trapdoor function) Ai cũng có thể rơi vào bẫy sập, nhưng chỉ mình ai biết cái chốt mở, mới ra đưọc mà thôi .

Vào năm 1975, Whitfield Diffie, Martin E. Hellman, và Ralph Merkle nhận thấy rằng hàm số bẫy sập có thể được dùng làm nền tảng cho việc mã hóa – hàm số mã hóa thì ai cũng có thể biết rõ , nhưng cách giải mã là một bí mật. Diffie và Hellman vào năm 1976 công bố một khảo cứu cho rằng cách mã hóa như thế là môt phương thế mã hóa không hoàn hảo. Vào năm 1978, Ronald Rivest, Adi Shamir, và Leonard Adleman , trong một công bố tại trường MIT, đã vạch ra những nét chính làm nền cho một cách mã hoá hoàn hảo.

Và như vậy , có lẽ đã đủ những kiến thức cần thiết để chúng ta bước vào chủ đế của buổi thuyết trình hôm nay : Hệ mã RSA


III. HỆ MÃ RSA

1-Nguyên tắc của hệ mã RSA

Với hệ mã RSA ,đầu tiên chúng ta cần phải có một cặp khóa lập mã chính là cặp ( e, m) trong đó m là tích của hai số nguyên tố rất lớn nào đó , m=p*q ,và e được chọn sao cho (e,Φ(m))=1 . Trong trường hợp này Φ(m) = (p -1 )*(q – 1) .Việc tại sao chúng ta lại phải chọn m như trên mà không chọn cách khác sẽ được nói sau , giờ chúng ta chỉ biết là nó liên quan đến tính bảo mật của mã.

Cũng cần phải nói thêm là với các loại mã như mã mũ hay mã RSA mà ta sắp xét thì ta không mã hóa từng chữ cái như với mã Caesar nữa mà thay vào đó là mã hóa từng khối chữ cái của văn bản .Xét ví dụ sau :
Ta có bảng chuyển tương ứng sau đây :

A B C D E F G H I J K L M
01 02 03 04 05 06 07 08 09 10 11 12 13

N O P Q R S T U V W X Y Z
14 15 16 17 18 19 20 21 22 23 24 25 26

Đầu tiên chuyển các chữ cái trong văn bản thành các số tương ứng , sau đó nhóm các số nhận được thành từng nhóm 2k chữ số tương ứng với k chữ cái trong văn bản ,và việc chọn k lại liên quan đến việc chọn m lúc đầu ,và chúng ta sẽ nói lại ở phần sau. Ví dụ ta lấy m=2
Tức là ta sẽ nhóm các chữ số lại thành từng khối 4 chữ số .(tương ứng với từng cặp 2 chữ cái )
Đối với một khối P trong văn bản ( là một số có 4 chữ số ) , để mã hóa ta lập khối C tương ứng bằng công thức sau :
E(P) ≡ C ≡ P^e (mod m ) , 0< C < m.

Từ một khối P trong văn bản ta đã mã hóa nó thành khối C

Để giải mã , ta cần phải biết một nghịch đảo d của e modulo Φ(m) .Nghịch đảo này tồn tại do
lúc đầu ta đã chọn e nguyên tố cùng nhau với Φ(m) .
Tức là tìm d sao cho e*d= 1 + k*Φ(m) . Khi đã có nghịch đảo d này ,ta có

D(C) ≡ C^d ≡ (P^e)^d ≡ P^ e*d ≡ P ^(1+ k*Φ(m)) ≡ P(mod m)

Trong đó P^Φ(m) ≡ 1 mod(m) , khi ( P , m) =1 . ( Xác suất để P va m không nguyên tố cùng nhau là rất nhỏ khi p,q chọn đủ lớn) . Cặp (d , m) được gọi là cặp khóa giải mã .

Để dễ hiểu ta xét ví dụ sau :

Lấy m =53*51=2703 => s = Φ(m) =52*50 = 2600
Chọn e= 3 , dĩ nhiên là (e, s) =1
Giả sử ta cần mã hóa thông báo sau :
DAY LA MA RSA

Trước tiên ta chuyển các chữ cái trong văn bản thành các chữ số và nhóm chúng lại thành từng khối như sau :

0401 2512 0113 0118 1901

( 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ữ X )

Mã hóa toàn bộ văn bản ta được văn bản mật sau đây :

1136 0463 2198 2311 1724

Để giải mã văn bản mật này ta cần tìm một nghịch đảo d của e modulo s=2600.
Dùng thuật toán Euclid mở rộng :

Cho a=2600 ; b= 3
u1 = 1 ; u2 = 0 ; u3 = 2600 ; v1 = 0 ; v2 = 1 ; v3 = 3
q = 866 u1 = 0 ; u2 = 1 ; u3 = 3 ; v1 = 1 ; v2 = -866 ; v3= 2
q = 1 u1 = 1 ; u2 = -866 ; u3= 2; v1 = -1 ; v2= 867 ; v3 = 1
q = 2 u1 = -1 ; u2 = 867 ; u3 = 1

suy ra (-1) * 2600 + 867 * 3 = 1

tức là ta có : 867 * 3 ≡ 1 ( mod 2600 ) => d = 867
Khi có d , ta giải mã từng khối C bằng công thức :

D(C) ≡ C^d ≡ P(mod m)

Ví dụ : 1136 ^ 867 ≡ (401^3) ^ 867 ≡ 401 ^(1 + 2600 ) ≡ 401 *401^ 2600 ≡
401 (mod 2703 )

Lưu ý là trong ví dụ của chúng ta , mọi khối P : 0401 ; 2512 ; 0113 ; 0118 ; 1901
đều nguyên tố cùng nhau với m = 2703 nên ta có P^ Φ(m) ≡ 1 (mod m )










Giờ ta sẽ nói kỹ hơn cách chọn các giá trị m , e , cũng như cách nhóm từng khối chữ số
Chú ý là để giải được mật mã thì phải tìm được d , mà để tìm d trước tiên ta phải tìm
được giá trị Φ(m) .
Đầu tiên là chọn m , ta phải lấy m là tích của hai số nguyên tố lớn vì các nguyên nhân sau :

Nếu chọn m chỉ là một số nguyên tố thôi thì người ta sẽ dễ dàng tìm được Φ(m) = m-1
Nếu đặt như vậy thì m chỉ có thể phân tích thành tích của hai số nguyên tố rất lớn .
Khi ta chọn p va q là các số nguyên tố khoảng 100 chữ số thì với những máy tính nhanh
nhất hiện nay , để phân tích được m cũng phải mất hàng tỷ năm .

Tiếp theo là việc chọn giá trị e và cách nhóm từng khối chữ số .
Với P là một khối đã được nhóm , P là một số có tối thiểu 2 chữ số .
Khi mã hóa P ta được C ≡ P^e (mod m) . Nếu P^e < m thì C = P^e ( với e công khai )
Như vậy để giải mã , ta chỉ cần tính căn bậc e của C ( tính theo cách thông thường ) .
Vì vậy khi đã có m , ta phải chọn e sao cho 2 ^ e > m . ( => P^e > m với mọi P )
Cũng vì lý do đó , ta cũng nên chọn cách nhóm sao cho P đủ lớn . Nhưng P không được vượt
quá m vì nếu P > m thì :
Khi giải mã một khối C : ta có D(C) ≡ P(mod m) ≡ P1 ( mod m) ( với P1 < m < P )
Ta không tìm được giá trị P ban đầu .

Tóm lại , chúng ta nên chọn m là tích của hai số nguyên tố rất lớn p và q , e là số nguyên tố tùy ý lớn hơn p và q .Nhất thiết phải chọn e thỏa điều kiện 2^e > m . Đối với các chữ số trong văn bản đầu , ta nhóm lại thành từng khối P có độ dài đủ lớn và P không được vượt
quá m .

Bây giờ ta sẽ cho thấy Hệ mã RSA là một hệ mã công khai :
Trong một nhóm cá thể cần trao đổi thông tin , mỗi cá thể sẽ chọn cho mình một cặp khóa lập
mã (e , m) và thông báo công khai , dĩ nhiên cặp khóa giải mã (d , m) chỉ có người này biết .
Các cá thể khác nếu chỉ biết e và m thì không thể nào tìm được d ( vì không thể phân tích được m ) .
(e , m) là cặp khóa công khai .
(d , m) là cặp khóa bí mật , phải được giữ kín .
Khi một cá thể nào đó muốn gửi thư mật cho cá thể I , anh ta chỉ cần mã hóa bức thư lại
theo công thức lập mã đã được công khai ( của cá I ) sau đó gửi đi . Cá thể I nhận đươc bức thư này , giải mã theo công thức giải mã của mình để biết nội dung. Nếu bức thư này rơi vào tay kẻ khác thì nội dung của nó vẫn đươc an toàn vì chỉ có cá thể I mới có khóa giải mã .

Ta nhắc lại lần nữa là nếu chỉ biết e và m , thì không cho phép tìm ra d . Vì để tìm được d ,
ta phải tìm được Φ(m) , và để tìm được Φ(m) thì ta phải phân tích m ra thừa số nguyên tố .


Nếu p và q là số lớn với chiều dài là 1024 bits, thì với những máy computer nhanh nhất hiện thời cũng phải mất hang tỷ năm mới có thể phân tích m ra thành p và q .

Nhưng có thể bạn sẽ đặt ra câu hỏi : nếu các số p ,q ,e quá lớn thì làm sao chúng ta có thể
thực hiên các phép tính với chúng . Ở ví dụ phần trước ta chỉ xét số lũy thừa e = 3 và tìm ra
được giá trị d= 867 , nhưng hoàn toàn không đi vào phần giải mã một cách cụ thể . Bây giờ
chúng ta sẽ tìm hiểu một phương pháp để tính toán modulo với những số mũ rất lớn .

Đó là phương pháp bình phương liên tiếp .

Xét ví dụ sau :


p= 61 <- số nguyên tố đầu tiên
q = 53 <- số nguyêntố thứ hai
p và q phải được giữ bí mật .

m=p*q = 3233
e = 17
e và m được thông báo công khai .
ta tìm được nghịch đảo của 17 modulo Φ(3233) là
d = 2753
d phải được giữ bí mật .
Chìa khóa công cộng là (e ,m).
Chìa khóa riêng là (e,m).

Hàm số mã hóa là:

mãhoá(P) ≡ (P^e) mod m
≡ (P^17) mod 3233

Hàm số giải mã là:

giảimã(C) ≡ (C^d) mod m
≡ (C^2753) mod 3233


Để mã hoá số “123”, làm như sau:

mãhoá(123) ≡ (123^17) (mod 3233 )
≡ 337587917446653715596592958817679803 (mod 3233 )
≡ 855

Như thế “123” được mã hóa thành “855”



Để giải mã “855”, làm như sau :

giảimã(855) ≡ (855^2753) ( mod 3233 )
≡ 123


Viết kết quả ngay ra đây, thì các bạn thấy qúa dễ dàng.
Vấn đề ở chỗ là tìm ra trị số của 855 khi được nâng lên luỹ thừa 2753 .

Đây là chỗ mà ta áp dụng phương pháp bình phương liên tiếp :

ta có 2753 = 1010110000012

2753 = 1 + 2^6 + 2^7 + 2^9 + 2^11
= 1 + 64 + 128 + 512 + 2048

Xét bản luỹ thừa sau đây 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)

Vậy:

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

Đây cũng chính là cách mà các máy tính của chúng ta làm việc để tính lũy thừa các số
nguyên .
Ưu điểm của nó là không bao giờ phải làm việc với nhũng số lớn hơn ( m – 1 )^2 .


Nếu các bạn có một chương trình điện toán như “bc” có sẵn trong Linux ,
bạn có thể tính 855^2753 mod 3233 trực tiếp như sau:

855^2753 mod 3233

Các bạn đoán xem kết quả sẽ như thế nào ?

Đây là kết quả :

855^2753 mod 3233
≡ 50432888958416068734422899127394466631453878360035 509315554967564501
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 635675558007116218
27727603182921790350290486090976266285396627024392 536890256337101471
68327404504583060228676314215815990079164262770005 461232291921929971
69907690169025946468104141214204472402661658275680 524166861473393322
65959127006456304474160852916721870070451446497932 266687321463467490
41185886760836840306190695786990096521390675205019 744076776510438851
51941619318479919134924388152822038464729269446084 915299958818598855
19514906630731177723813226751694588259363878610724 302565980914901032
78384821401136556784934102431512482864529170314100 400120163648299853
25166349056053794585089424403855252455477792240104 614890752745163425
13992163738356814149047932037426337301987825405699 619163520193896982
54478631309773749154478427634532593998741700138163 198116645377208944
00285485000269685982644562183794116702151847721909 339232185087775790
95933267631141312961939849592613898790166971088102 766386231676940572
95932538078643444100512138025081797622723797210352 196773268441946486
16402961059899027710532570457016332613431076417700 043237152474626393
99011899727845362949303636914900881060531231630009 010150839331880116
68215163893104666659513782749892374556051100401647 771682271626727078
37012242465512648784549235041852167426383189733332 434674449039780017
84689726405462148024124125833843501704885320601475 687862318094090012
63241969092252022679880113408073012216264404133887 392600523096072386
15855496515800103474611979213076722454380367188325 370860671331132581
99227975522771848648475326124302804177943090938992 370938053652046462
55147267884961527773274119265709116613580084145421 487687310394441054
79639308530896880365608504772144592172500126500717 068969428154627563
70458838904219177398190648731908014828739058159462 227867277418610111
02763247972904122211994117388204526335701759090678 628159281519982214
57652796853892517218720090070389138562840007332258 507590485348046564
54349837073287625935891427854318266587294608072389 652291599021738887
95773647738726574610400822551124182720096168188828 493894678810468847
31265541726209789056784581096517975300873063154649 030211213352818084
76122990409576427857316364124880930949770739567588 422963171158464569
84202455109029882398517953684125891446352791897307 683834073696131409
74522985638668272691043357517677128894527881368623 965066654089894394
95161912002160777898876864736481837825324846699168 307281220310791935
64666840159148582699993374427677252275403853322196 852298590851548110
40229657916338257385513314823459591633281445819843 614596306024993617
53097925561238039014690665163673718859582772525683 119989984646027216
46279764077057074816406450769779869955106180046471 937808223250148934
07851137833251073753823403466269553292608813843895 784099804170410417
77608463062862610614059615207066695243018438575031 762939543026312673
77406936404705896083462601885911184367532529845888 040849710922999195
65539701911191919188327308603766775339607722455632 113506572191067587
51186812786344197572392195263333856538388240057190 102564949233944519
65959203992392217400247234147190970964562108299547 746193228981181286
05556588093851898811812905614274085809168765711911 224763288658712755
38928438126611991937924624112632990739867854558756 652453056197509891
14578114735771283607554001774268660965093305172102 723066635739462334
13638045914237759965220309418558880039496755829711 258361621890140359
54234930424749053693992776114261796407100127643280 428706083531594582
305946326827861270203356980346143245697021484375 mod 3233
≡ 123

Kết quả là một số với 8072 chữ số.

Đó mới chỉ với hai số P =61 và Q =53 .



2-Một số biến thể của RSA

Hệ mã RSA là một hệ mã có tính an toàn rất cao . Nhưng nó có một 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ể
mà ta sẽ nói qua dưới đây .

Xác nhận chủ thể là việc đả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ư.
Để 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 . Ở đây ta chỉ nói sơ qua về hàm băm vì nó vượt quá nội dung của bài này .
Ta chỉ biết đó 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 …

IV. TỔNG KẾT

Dù là hệ mã công khai xuất hiện đầu tiên , nhưng cho đến nay hệ mã RSA vẫn cho thấy là
một hệ mã rất an toàn . Tính an toàn của nó dựa trên bài toán Phân tích số nguyên .

Mà thuật toán phân tích một số nguyên m thành thừa số lại cần đến một thời gian tăng theo cấp số luỹ thừa so với chiều dài của m . Nghĩa là nếu chỉ thêm cho m vài ký tự, thời gian cần để đặt m thành thừà số sẽ tăng gấp đôi. Vì khi thêm vài ký tự vào R là làm cho nó lớn thêm hàng trăm hay ngàn lần nhiều hơn, tức là gia tăng danh sách các cặp thừa số có thề dùng làm
p và q .

Vậy nếu giả như bất ngờ có ai tìm ra được một kỹ thuật mới giúp cho việc đặt thành thừa số có thể thực hiện hàng tỷ tỷ lần nhanh hơn, thì ta chỉ cần chọn một số m khác dài hơn chừng mười ký tự, tình trạng sẽ trở lại như ban đầu ...

Thuật toán RSA chỉ bị phá vỡ khi tìm được một cách nào đó cho ta trực tiếp các thừa số nguyên tố của một số . Cho đến bây giờ việc đó chưa được chứng minh là bất khả. Nhưng nếu chúng ta biết rằng các số nguyên tố đã được nghiên cứu từ cả ngàn năm nay, và trong vòng vài thập niên qua được nghiên cứu rầm rộ trở lại. thì câu trả lời có vẻ còn rất xa vời. Nhưng nếu tìm ra được một phương pháp như thế, thì thuật toán mã hoá sẽ bị thay đổi toàn diện .

Sau khi hệ mã RSA xuất hiện , đã có rất nhiều hệ mã công khai khác được ra đời với rất nhiều cải tiến . Và với sự phát triển của mật mã khóa công khai , có lẽ sẽ có lúc việc mã hóa không còn là việc xa lạ với mọi người nữa , mà có thể mã hóa sẽ được áp dụng rộng rãi trong đời sống chúng ta . Có thể lúc đó , trong danh thiếp của mỗi người , ngoài số điện thoại và địa
chỉ , còn có thêm khóa lập mã của họ.



Nhắc nhở.. lần sau post bài nhớ ghi rõ tiêu đề