Đồ án Nghiên cứu kỹ thuật che giấu tin trong tài liệu số hoá

MỤC LỤC Chương 1: VẤN ĐỀ MÃ HOÁ THÔNG TIN………………………………..4 1.1 KHÁI NIỆM MÃ HOÁ…………………………………………………..4 1.1.1 Định nghĩa………………………………………………………….4 1.1.2 Phân loại……………………………………………………………6 1.2 HỆ MÃ HOÁ ĐỐI XỨNG…………………………………………….....7 1.2.1 Hệ mã hoá đối xứng cổ điển....……………………………………...7 1.2.1.1 Mã dịch vòng……………………………………………………7 1.2.1.2 Mã thay thế……………………………………………………...8 1.2.1.3 Mã Affine…………………………………………………….....9 1.2.1.4 Mã Vigenere…………………………………………………...10 1.2.1.5 Mã Hill………………………………………………………...11 1.2.1.6 Mã hoán vị…………………………………………………….12 1.2.1.7 Mã dòng……………………………………………………….13 1.2.2 Hệ mã hoá đối xứng hiện đại………………………………………14 1.2.2.1 Mã theo chuỗi bit………………………………………………14 1.2.2.2 Mã theo chữ……………………………………………………14 1.2.2.3 Mã theo khối…………………………………………………...15 1.2.2.4 Mã mũ…………………………………………………………15 1.2.2.5 DES……………………………………………………………16 1.3 HỆ MÃ HOÁ CÔNG KHAI……………………………………………..17 1.3.1 Hệ mật mã RSA…………………………………………………....17 1.3.1.1 Định nghĩa sơ đồ hệ mật……………………………………….17 1.3.1.2 Thực hiện hệ mật………………………………………………18 1.3.1.3 Các phương pháp tấn công hệ mật……………………………..18 1.3.2 Hệ Elgamal……………………………………………………........19 Chương 2: VẤN ĐỀ GIẤU TIN………………………………………………..20 2.1 KHÁI NIỆM VỀ GIẤU TIN....…………………………………………..20 2.1.1 Khái niệm thông tin “số hoá”……………………………………..20 2.1.2 Khái niệm giấu tin…………………………………………………21 2.1.3 Mô hình giấu tin…………………………………………………....22 2.1.3.1 Mô hình giấu tin vào phương tiện chứa………………………..22 2.1.3.2 Mô hình tách tin từ phương tiện chứa………………………….23 Một số thuật ngữ cơ bản……………………………………………………...24 2.1.4 Phân loại kỹ thuật giấu tin………………………………………...25 2.1.4.1 Phân loại theo phương tiện chứa……………………………….25 2.1.4.2 Phân loại theo cách thức tác động lên phương tiện…………….25 2.1.4.3 Phân loại theo mục đích sử dụng………………………………25 2.1.5 Các thành phần trong kỹ thuật giấu tin…………………………..26 2.1.5.1 Phương tiện chứa tin…………………………………………...26 2.1.5.2 Thông tin cần che giấu…………………………………………27 2.1.5.3 Khoá giấu tin…………………………………………………..27 2.2 CÁC GIAO THỨC GIẤU TIN…………………………………………..28 2.2.1 Giấu tin thuần tuý………………………………………………….28 2.2.2 Giấu tin sử dụng khoá bí mật……………………………………...29 2.2.3 Giấu tin với khoá công khai……………………………………….30 2.3 GIẤU TIN TRONG DỮ LIỆU ĐA PHƯƠNG TIỆN…………………..31 2.3.1 Giấu tin trong ảnh…………………………………………………31 2.3.2 Giấu tin trong audio……………………………………………….32 2.3.2 Giấu tin trong video……………………………………………….33 2.4 PHƯƠNG PHÁP GIẤU TIN TRONG MÔI TRƯỜNG ĐA PHƯƠNG TIỆN….34 2.4.1 Một số ký hiệu…………………………………………………….34 2.4.2 Nguyên lý giấu tin bằng cách thay thế……………………………35 2.4.3 Thay đổi các bit ít quan trọng nhất……………………………….37 2.4.4 Phương pháp giấu tin vào các vùng của phương tiện chứa……...41 2.4.5 Hoán vị giả ngẫu nhiên…………………………………………….44 2.4.6 Giảm chất lượng ảnh để giấu tin…………………………………..46 2.4.7 Giấu tin trong ảnh màu……………………………………………47 2.4.7.1 Giấu tin trong các định dạng ảnh dùng bảng màu……………...47 2.4.7.2 Giấu tin trong các ảnh màu thông thường……………………...49 Những thuật ngữ viết tắt……………………………………………………...50 Chương 1 VẤN ĐỀ MÃ HOÁ THÔNG TIN 1.1 KHÁI NIỆM MÃ HOÁ 1.1.1 Định nghĩa Đối tượng cơ bản của mật mã là tạo ra khả năng liên lạc trên một kênh không mật cho hai người sử dụng (có thể gọi là S (Sender) và R (Receiver)) sao cho đối phương T không hiểu được thông tin được truyền đi. Kênh này có thể là một đường dây điện thoại hoặc một mạng máy tính. Thông tin mà S muốn gửi cho R (bản rõ) có thể ở bất kỳ dạng dữ liệu nào. S sẽ mã hoá bản rõ bằng một khoá đã được xác định trước và gửi bản mã trên kênh. T có bản mã thu trộm được trên kênh, song “khó” thể xác định được nội dung bản rõ. R (là người biết khoá) có thể giải mã và thu được bản rõ. Định nghĩa hệ mật mã Hệ mật mã là một bộ 5 (P, C, K, E, D) thoả mãn các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể. 2. C là tập hữu hạn các bản mã có thể. 3. K (không gian khoá) là tập hữu hạn các khoá có thể. 4. Đối với mỗi k
K có một quy tắc mã: P → C và một quy tắc giải mã tương ứng dk
D. Mỗi ek: P → C và dk: C → P là những hàm mã: dk (ek (x)) = x với mọi bản rõ x
P. Tính chất 4 là tính chất chủ yếu. Nội dung của nó là nếu một bản rõ x được mã hoá bằng ek và bản mã nhận được sau đó được giải mã bằng dk thì ta phải thu được bản rõ ban đầu x. S và R sẽ áp dụng thủ tục sau dùng hệ mật khoá riêng. Trước tiên họ chọn ngẫu nhiên một khoá k
K. Điều này thực hiện khi họ ở cùng một chỗ và không bị T theo dõi, hoặc khi họ có một kênh mật trong trường hợp ở xa nhau. Sau đó giả sử S muốn gửi một thông báo cho R trên một kênh không mật và ta xem thông báo này là một chuỗi: x = x1, x2, …, xn với số nguyên n ≥ 1 nào đó. Ở đây mỗi một ký hiệu của bản rõ x
P, 1 ≤ i ≤ n. Mỗi xi sẽ được mã hoá bằng quy tắc mã ek với khoá k xác định trước đó. Bởi vậy, S sẽ tính y = ek (xi), 1 ≤ i ≤ n và chuỗi bản mã nhận được y = y1y2…yn , sẽ được gửi trên kênh. Khi R nhận được y = y1y2…yn anh ta sẽ giải mã dk và thu được bản rõ gốc x1x2…xn. Hình 1: Kênh liên lạc Rõ ràng là trong trường hợp này hàm mã hoá ek phải là hàm đơn ánh (tức là ánh xạ 1 - 1). Nếu không việc giải mã sẽ không thể thực hiện được một cách tường minh. 1.1.2 Phân loại Các hệ thống mã hoá phổ biến thuộc một trong hai loại sau: Mã hoá với khoá đối xứng (Symmetric-key Encryption) Mã hoá với khoá công khai (Public-key Encryption) Mã hóa đối xứng là hệ mã hoá mà biết được khoá lập mã thì “dễ ” tính khoá giải mã và ngược lại. Trong một số trường hợp, hệ mã hoá khoá đối xứng có khoá lập mã và khoá giải mã trùng nhau. Mã hóa với khoá công khai sử dụng hai khóa khác nhau thực sự, để mã hóa và giải mã thông tin. Tức là biết khoá này “khó” tính được khoá kia. Mỗi hệ thống mã hóa có ưu nhược điểm riêng. Mã hóa với khoá đối xứng xử lí nhanh, nhưng độ an toàn không cao. Mã hóa với khoá công khai xử lí chậm hơn, nhưng độ an toàn và tính thuân tiện trong quản lí khóa cao. Trong các ứng dụng mã hóa hiện tại, người ta thường kết hợp các ưu điểm của cả hai loại mã hóa này. 1.2 HỆ MÃ HOÁ ĐỐI XỨNG 1.2.1 Hệ mã hoá đối xứng cổ điển 1.2.1.1 Mã dịch vòng Ta sẽ mô tả mã dịch vòng dựa trên số học module. Ta định nghĩa Zm là tập các số nguyên từ 0 đến m – 1, ký hiệu đó cũng dùng cho các số nguyên từ 0 đến m – 1 với các phép cộng và nhân theo mod m. Việc cộng và nhân trong Zm được thực hiện giống như cộng và nhân các số thực ngoại trừ một điểm là các kết quả sẽ được rút gọn theo module m. Mã dịch vòng được xác định trên Z25 (do có 26 chữ cái trên bảng chữ cái tiếng Anh) mặc dù vậy có thể xác định nó trên Zm với module m tuỳ ý. Định nghĩa: Giả sử P = C = Z26 với 0 ≤ k ≤ 25 ek(x) = x + K mod 26 và dk(x) = y – K mod 26 (x, y
Z26) Trong trường hợp K = 3, hệ mật mã thường được gọi là hệ mã Caesar đã được Julius Caesar sử dụng. Ta sẽ sử dụng mã dịch vòng (với module 26) để mã hoá một văn bản tiếng Anh thông thường bằng cách thiết lập sự tương ứng giữa các kí tự và các thặng dư theo module 26 như sau: A
0, B
1, …, Z
25. A  B  C  D  E  F  G  H  I  J  K  L  M   0  1  2  3  4  5  6  7  8  9  10  11  12   N  O  P  Q  R  S  T  U  V  W  X  Y  Z   13  14  15  16  17  18  19  20  21  22  23  24  25   1.2.1.2 Mã thay thế Một hệ mã nổi tiếng khác là hệ mã thay thế. Định nghĩa: Cho P = C = Z26. K chứa mọi hoán vị có thể của 26 kí hiệu 0, 1, …, 25 Với mỗi phép hoán vị π
K, ta định nghĩa: eπ(x) = π (x) và dπ(y) = π-1(y) trong đó π-1 là hoán vị ngược của π. Sau đây là một ví dụ về phép hoán vị ngẫu nhiên π tạo nên một hàm mã hoá (các kí hiệu của bản rõ được viết bằng chữ thường còn các kí tự của bản mã là chữ in hoa). a  b  c  d  e  f  g  h  i  j  k  l  m   X  N  Y  A  H  P  O  G  Z  Q  W  B  T   n  o  p  q  r  s  t  u  y  w  x  y  z   S  F  L  R  C  V  M  U  E  K  J  D  I   Như vậy, eπ(a) = X, eπ(b) = N,…hàm giải mã là phép hoán vị ngược. Điều này được thực hiện bằng cách viết hàng thứ hai lên trước rồi sắp xếp theo thứ tự chữ cái. Ta nhận được: A  B  C  D  E  F  G  H  I  J  K  L  M   d  l  r  y  v  o  h  e  z  x  w  p  T   N  O  P  Q  R  S  T  U  V  W  X  Y  Z   b  g  f  j  q  n  m  u  s  k  a  c  I   Bởi vậy dπ(A) = d, dπ(B) = l,… 1.2.1.3 Mã Affine Mã dịch vòng là một trường hợp đặc biệt của mã thay thế chỉ gồm 26 trong số 26! các hoán vị có thể của 26 phần tử. Một trường hợp đặc biệt khác của mã thay thế là mã Affine được mô tả dưới đây. Trong mã Affine, ta giới hạn chỉ xét các hàm mã có dạng: e(x) = a * x + b mod 26 (a, b
Z26. Các hàm này được gọi là hàm Affine, chú ý rằng khi a = 1 ta có mã dịch vòng). Định nghĩa: Cho P = C = Z26 và giả sử K = {(a, b)
Z26 × Z26: UCLN (a, 26) = 1} Với K = (a, b)
K ta định nghĩa: ek(x) = a * x + b mod 26 và dk(y) = a-1 (y - b) mod 26 với x, y
Z26 Để có được phép giải mã tương ứng, tức để cho phương trình: a * x + b = c mod 26 có lời giải đối với x (với bất kì c cho trước) thì điều kiện cần và đủ là a nguyên tố với 26, tức UCLN(a, 26) = 1. Khi UCLN (a, 26) = 1, thì có số a-1
Z26 sao cho a * a-1 = a-1 * a = 1 mod 26 và do đó, nếu y = a * x + b mod 26, thì x = a-1 (y - b) mod 26 và ngược lại. 1.2.1.4 Mã Vigenere Trong cả hai hệ mã dịch vòng và mã thay thế (một khi đã được chọn) mỗi kí tự sẽ được ánh xạ vào một kí tự duy nhất. Vì lý do đó, các hệ mật mã còn lại được gọi là hệ thay thế đơn biểu. Bây giờ ta sẽ trình bày một hệ mật mã không phải là bộ chữ đơn, đó là hệ mật mã Vigenere nổi tiếng. Mật mã này lấy tên của Blaise de Vigenere sống vào thế kỷ 16. Sử dụng phép tương ứng A
0, B
1,…, Z
25 mô tả ở trên, ta có thể gắn cho mỗi khoá K với một chuỗi kí tự có độ dài m được gọi là từ khoá. Mã Vigenere sẽ mã hoá đồng thời m kí tự: Mỗi phần tử của bản rõ tương đương với m kí tự. Định nghĩa: Cho m là một số nguyên dương cố định nào đó. P = C = K = (Z26)m. Với khoá K = (k1, k2,…, km) ta xác định: ek(x1, x2,…, xm) = (x1 + k1, x2 + k2,…, xm + km) và dk(y1, y2,…, ym) = (y1 – k1, y2 – k2,…, ym - km) trong đó tất cả các phép toán được thực hiện trong Z26. 1.2.1.5 Mã Hill Trong phần này sẽ mô tả một hệ mật thay thế đa biểu khác đựoc gọi là mật mã Hill. Mật mã này do Lester S.Hill đưa ra vào năm 1929. Giả sử m là một số nguyên dương, đặt P = C = (Z26)m. Ý tưởng ở đây là lấy m tổ hợp tuyến tính của m kí tự trong một phần tử của bản rõ để tạo ra m kí tự ở một phần tử của bản mã. Như vậy, khoá sẽ được cho bởi một ma trận cấp m, tức là một phần tử của Z26m*n. Để phép biến đổi tuyến tính xác định bởi ma trận K
Z26m*n có phép nghịch đảo, ma trận K cũng phải có phần tử nghịch đảo K-1
Z26m*n. Điều kiện cần và đủ để ma trận K có ma trận nghịch đảo là định thức của nó, kí hiệu det K nguyên tố với m. Định nghĩa: Cho m là số nguyên dương. P = C = Z26m, К = {K
Z26m*n: (det K, 26) = 1 } Với mỗi K
К, ta có: ek (x1, x2, …, xm) = (x1, x2, …, xm) * K và dk (y1, y2, …, ym) = (y1, y2, …, ym) * K-1. 1.2.1.6 Mã hoán vị Tất cả các hệ mật mã trên ít nhiều đều xoay quanh phép thay thế: các kí tự của bản rõ được thay bằng các kí tự khác trong bản mã. Ý tưởng của mã hoán vị là giữa các kí tự của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng cách sắp xếp lại các vị trí này. Mã hoán vị (còn được gọi là mã chuyển vị) đã được dùng từ hàng trăm năm nay. Thật ra thì sự phân biệt giữa mã hoán vị và mã thay thế đã được Giovani Porta chỉ ra từ những năm 1563. Không giống như mã thay thế, ở đây không có các phép toán đại số nào cần thực hiện khi mã hoá và giải mã nên thích hợp hơn cả là dùng luôn các kí tự mà không dùng các thặng dư theo module 26. Định nghĩa: Cho m là một số nguyên dưong xác định nào đó. Cho P = C = (Z26)m và К gồm tất cả các hoán vị của {1, …, m}. Đối với một khoá π (tức là một hoán vị) ta xác định: eπ (x1, …, xm) = (xπ(1), …, xπ(m)) và dπ (y1, …, ym) = (yπ-1(1), …, yπ-1(m)) trong đó π-1 là hoán vị ngược của π. 1.2.1.7 Mã dòng Trong các hệ mật mã nghiên cứu ở trên, các phần tử liên tiếp của bản rõ đều được mã hoá bằng cùng một khoá K. Tức xâu bản mã y nhận được có dạng: y = y1y2y3…. = ek (x1) ek (x2)…. Các hệ mật mã thuộc dạng này thường được gọi là các mã khối. Một quan điểm sử dụng khác là mật mã dòng. Ý tưởng cơ bản ở đây là tạo ra một dòng khoá z = z1z2… và dùng nó để mã hoá một xâu bản rõ x = x1x2…. theo quy tắc: y = y1y2y3…. =
(x1)
(x2)….
Mã dòng hoạt động như sau: Giả sử k
K là khoá và x1x2.... là xâu bản rõ. Hàm fi được dùng để tạo zi (zi là phần tử thứ i của dòng khoá) trong đó fi là một hàm của khoá K và i – 1 kí tự đầu tiên của bản rõ. z = fi (K, x1, …, xi - 1) Phần tử zi của dòng khoá được dùng để mã xi tạo ra yi = ezi (xi). Bởi vậy, để mã hoá xâu bản rõ x1x2.... ta phải tính liên tiếp: z1, y1, z2, y2… Việc giải mã xâu bản mã y1y2…. có thể được thực hiện bằng cách tính liên tiếp: z1, x1, z2, x2…. Định nghĩa: Mật mã dòng là một bộ (P, C, K, L, F, E, D) thoả mãn các điều kiện sau: P là tập hữu hạn các bản rõ có thể C là tập hữu hạn các bản mã có thể K là tập hữu hạn các khoá có thể (không gian khoá) L là tập hữu hạn bộ chữ của dòng khoá F = (f1f2….) là bộ toạ dòng khoá. (Với i ≥ 1) fi : K × P-1 → L Với mỗi z
L có một quy tắc mã ez
E và một quy tắc giải mã tương ứng dz
D. (ez : P → C và dz : C → P là một hàm thoả mãn dz (ez (x)) = x với mọi bản rõ x
P ). 1.2.2 Hệ mã hoá đối xứng hiện đại 1.2.2.1 Mã theo chuỗi bit Trong hệ mã theo chuỗi bit, thông điệp là các bit và khoá được phát sinh bởi một bộ phát sinh bit ngẫu nhiên. Bản rõ được mã hoá theo từng bit một để được bản mã: M K  0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0… 1 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1…   C  1 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1…   Khoá được cung cấp cho bộ phát sinh bit ngẫu nhiên để tạo ra dãy tín hiệu nhị phân. Chuỗi bit khoá K sau đó được trộn với bản rõ M, thường theo phép XOR (phép cộng mod 2), để sinh ra bản mã C. Giải mã được thực hiện bằng cách XOR bản mã với cùng khoá K do sử dụng bộ phát sinh chuỗi bit ngẫu nhiên tạo ra: C K  1 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1… 1 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1…   M  0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0…   1.2.2.2 Mã theo chữ Các hệ mã ban đầu thường dựa trên cơ sở phép biến đổi một chữ cái trong bản rõ thành một chữ cái khác trong bản mã. Kỹ thuật mã hoá này còn được gọi là mã thay thế, do một ký tự được chuyển thành một ký tự khác bằng cách thay thế. Để thực hiện phương pháp này, cần định nghĩa một bảng mã (như bảng mã ASCII) để số hoá bản rõ, vì các phép toán này làm việc trên các số thay vì các ký tự. Minh hoạ: A B C D E F G H I K L … R S T U V W X Y Z 00 01 02 03 04 05 06 07 08 09 10 …17 18 19 20 21 22 23 24 25 1.2.2.3 Mã theo khối Trong mã khối, bản rõ và bản mã được chia thành từng khối ký tự trước khi thi hành mã hóa và giải mã. Kỹ thuật mã theo khối được mô tả như sau: - Chia văn bản M thành nhiều khối, M = M1M2…Mj, mỗi khối Mi, 1 ≤ i ≤j là một khối n ký tự. - Chuyển các ký tự thành các số tương đương và xây dựng bản mã: Ci = AMi + B( mod n), i = 1,2,…,j Trong đó, (A, B) là khoá, A là một ma trận khả nghịch cấp n, với gcd(det(A), n) = 1, B = (B1, B2,…, Bn)T, C = (c1, c2, …, cn) và Mi = (m1, m2,…, mn)T. - Để giải mã, ta thi hành phép toán: Mi = A-1(Ci - B)(mod n). trong đó A-1 là ma trận nghịch đảo của A. 1.2.2.4 Mã mũ Mã mũ do Pohlig và Hellman giới thiệu năm 1976, có thể được mô tả như sau. Chọn p là số nguyên tố, M là một số tương ứng của bản rõ với mỗi ký tự trong bản rõ được thay thế bằng mã tương ứng như trong bảng (có mở rộng để xử lý ký tự trắng): ‘‘ A B C D E F G H I K L … R S T U V W X Y Z 00 01 02 03 04 05 06 07 08 09 10 11 …18 19 20 21 22 23 24 25 26 - Chia M thành các khối Mi, 0 < Mi < p. Gọi k là một số nguyên thoả mãn 0 < k < p và gcd (k, p-1) = 1. - Mã hoá khối Mi thành: Ci = E(k,Mi)
Mik (mod p) - Ci được giải mã theo công thức Mi = D(v,Ci)
Civ
(Mik)v
Mi (mod p) trong đó, kv
1 (mod p-1). 1.2.2.5 DES Mô hình mã khoá bí mật (mã hoá đối xứng) phổ biến nhất đang được sử dụng là DES – Data Encryption Standard - được IBM đề xuất và được uỷ ban Chuẩn Quốc gia Mỹ, hiện gọi là Viện Quốc gia về chuẩn và công nghệ (NIST), chấp nhận như một chuẩn chính thức. DES sử dụng một phép toán hoán vị, thay thế, và một số toán tử phi tuyến. Các phép toán tử phi tuyến này được áp dụng (16 lần) vào từng khối của thông điệp 32 bit. Bản rõ, trước hết, được chia thành các khối thông điệp 64 bit. Khoá sử dụng 56 bit nhận được từ khoá bí mật 64 bit, có chứa 8 bit kiểm tra chẵn lẻ. Thuật giải giải mã được thực hiện theo chiều ngược lại, với cùng một khoá bí mật đã dùng khi mã hóa. 1. 3 HỆ MÃ HOÁ KHOÁ CÔNG KHAI Phương pháp mã hoá công khai là sự phối hợp giữa một khoá riêng (Private Key) và một khoá công khai (Public Key). Khoá riêng chỉ được biết bởi mỗi máy tính, trong khi khoá công khai được máy tính này cung cấp cho các máy tính khác giao tiếp với nó. Để giải mã một thông điệp đã mã hoá, máy tính nhận thông điệp phải dùng khoá bí mật. 1.3.1 Hệ mật mã RSA 1.3.1.1 Định nghĩa sơ đồ hệ mật Hệ mật mã RSA sử dụng các tính toán trong Zn, trong đó n là tích của 2 số nguyên tố phân biệt p và q. Ta nhận thấy rằng
= (p - 1)(q - 1). Định nghĩa: Cho n = p * q với p, q là số nguyên tố lớn. Đặt P = C = Zn Chọn b nguyên tố với
,
= (p - 1)(q - 1). K = {(n, a, b): a * b
1 (mod
)}. Giá trị n và b là công khai, và a là bí mật Với mỗi K = (n, a, b), mỗi x
P, y
C, ta có: Hàm mã hoá: y = ek(x) = xb mod n Hàm giải mã: dk (x) = ya mod n 1.3.1.2 Thực hiện hệ mật Có nhiều khía cạnh cần thảo luận về hệ mật mã RSA, bao gồm các chi tiết về việc thiết lập hệ mật mã, tính hiệu quả của phép mã và giải mã và độ mật của hệ. Để thiết lập hệ thống, R sẽ tuân theo các bước sau: R tạo 2 số ngưyên tố lớn p và q R tính n = p * q và
= (p - 1)(q - 1) R chọn một số ngẫu nhiên b (1 < b <
) sao cho UCLN(b,
) = 1 R tính a = b-1 mod
dùng thuật toán Euclide mở rộng R công bố n và b trong một danh bạ và dùng chúng làm khoá công khai. 1.3.1.3 Các phương pháp tấn công hệ mật Cách tấn công dễ thấy nhất đối với hệ mật mã này là thám mã cố gắng phân tích n ra các thừa số nguyên tố. Nếu thực hiện được phép phân tích này thì có thể dễ dàng tính được
= (p -1)*(q - 1) và tính số mũ a và b đúng như R làm. Vì thế để hệ RSA được coi là mật thì nhất thiết n = p*q phải là một số đủ lớn để việc phân tích nó sẽ không có khả năng về mặt tính toán. Vì vậy để đảm bảo an toàn, nên chọn các số p và q có chừng 100 chữ số, khi đó n sẽ có tới 200 chữ số. Phép mã (hoặc giải mã) sẽ xoay quanh phép lấy luỹ thừa theo module n. Vì n là một số rất lớn nên ta phải sử dụng số học lấy chính xác nhiều lần để thực hiện các tính toán trong Zn và thời gian tính toán cần thiết sẽ phụ thuộc vào số các bit trong biểu diễn nhị phân của n. 1.3.2 Hệ Elgamal Năm 1985, Elgamal đề nghị một hệ mã khoá công khai dựa trên bài toán logarithm rời rạc. Chúng ta sẽ bắt đầu bằng việc mô tả bài toán này khi thiết lập một trường hữu hạn Zp, p là số nguyên tố. Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ thể là không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời rạc. Để gây khó khăn cho các phương pháp tấn công đã biết, p phải có ít nhất 150 chữ số và p – 1 phải có ít nhất một thừa số nguyên tố lớn. Lợi thế của bài toán logarithm rời rạc trong xây dựng hệ mật là khó tìm được các logarithm rời rạc, song bài toán ngược lấy luỹ thừa lại có thể tính toán hiệu quả cao theo thuật toán nhân và bình phương. Nói cách khác, luỹ thừa theo module p là hàm một chiều với các số nguyên tố p thích h