Thắc mắc về ước số chung lớn nhất thuật toán affine

Thuật toán affine encryption chỉ cần khoá là 2 số a, b.

encrypt(x) = (ax+b) % 26 // 26 là tổng chữ cái alphabet

decrypt(x)= a^-1(y-b)%26

Chọn a sao cho gcd(a,26)=1, b bất kỳ.

Vậy cho em hỏi tại sao trong trường hợp này này a^-1 là 21 mà không phải 1/5 ? Em cảm ơn

đây là vì người viết bài thiếu kiến thức (hoặc cũng có thể do nhầm lẫn)
đó không phải là phép lũy thừa -1 (hay còn được hiểu là phép nghịch đảo)
đó là nghich đảo đồng dư, bạn có thể search google để biết cách tìm

3 Likes

là do hệ thống số này nó vậy. Gọi số x, y thuộc tập hợp đồng dư của n (chỉ có giá trị là số nguyên từ 0 tới n-1) thì ta có:

  • x+y (mod n) cũng thuộc tập hợp đồng dư của n
  • x-y (mod n) cũng thuộc tập hợp đồng dư của n
  • x*y (mod n) cũng thuộc tập hợp đồng dư của n
  • x/y (mod n) cũng thuộc tập hợp đồng dư của n

x/y chính là x*y^-1, nếu cho x=1 thì x*y^-1 = y^-1 cũng phải thuộc tập hợp đồng dư của n nên y^-1 cũng phải có giá trị từ 0 tới n-1. Vậy nên ở đây x=5, n=26 thì x^-1 phải có giá trị từ 0 tới 26-1, ở đây tính ra là 21 vì x*x^-1 = 5*26 = 105 chia 26 dư 1. Chọn x^-1 = 21 vì nó có tính chất x*x^-1 = 1 (mod n) ấy :V

5 Likes

Mình hỏi ké, vậy chỉ còn cách dùng Brute force cho chạy từ 0 tới 26 để mò nghiệm thôi phải không anh?
Mình tìm được lời giải đây

Với lại cái này được xếp vào mã hoá một chiều đúng không?

có thuật toán Extended Euclid gì đấy à ra lẹ mà :V

điều kiện là x và n phải là số ng tố cùng nhau.

5 Likes

Hai chiều :smiley: Số nhân vào phải có nghịch đảo modulo, nói cách khác là nguyên tố cùng nhau với modulo.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?