Bây giờ là 00:04 ngày 5-4-2017. hahahahaha…. Vừa mới hăng máu lên ngồi miệt mài theo tới cùng để tìm cho được cách tính d trong giải thuật RSA. Và dĩ nhiên, công sức đổ ra không hao phí. Cuối cùng cũng hiểu được làm cách nào tính ra d rồi! yeye ^^

Chuyện là hồi trưa nằm đọc cuốn Mật mã – Từ cổ điển đến lượng tử của tác giả Simon Singh do NXB Trẻ phát hành. Nó đây.

_MG_9430

Mua gần 3 năm mà bây giờ mới đọc được chừng nửa cuốn thôi. Thích thật nhưng khó nuốt khiếp.

Giải thuật mã hoá bất đối xứng RSA này do ba nhà tạo mã tạo mã phát minh ra. Ronald Rivest, Adi Shamir và Leonard Adleman nhưng thật ra người viết ra giải thuật đó đầu tiên là Rivest (do vậy mà tên ông đứng đầu). Nhưng cần phải làm rõ 1 ý chính: họ chỉ là người đưa ý tưởng mã bất đối xứng ra thành thực nghiệm thành công, chứ không phải là người khởi nguyên ý tưởng. Muốn hiểu rõ hơn chứ gì, mua sách đọc đi =)))

Bây giờ để không quên công sức ngồi mò mẫm ra, tôi viết lại những gì cần làm để thực hiện chính xác giải thuật của họ đưa ra như sau.

ct.PNG

Công thức để triển khai chỉ có như vậy thôi, mà nhóm tác giả mất hơn năm trời mới tìm ra, sau khi xé bỏ rất nhiều bản thảo ý tưởng. Cũng lại là chuyện tình tay ba siêu kinh điển trong giới mật mã học: Alice – Bob – Eve.

Alice và Bob đang yêu nhau mặn nồng (hiện tại là như thế, còn sau này thế nào, ai thay lòng đổi dạ hay chán chê rồi, cảm thấy nhạt rồi, hết yêu rồi *yêu mà cũng có còn yêu với hết yêu mới ghê chứ* hay chán chê rồi thì ai mà biết được). Còn Eve? Nàng ấy là ai? Chỉ là một cô bé trong sáng ngây thơ hiền lành ngốc nghếch ngồi ở nhà bật laptop lên và cố….bắt lén thư điện tử hai anh chị kia trao đổi nhau. Eve yêu thầm Bob. Thế mới khổ. Yêu mà không dám nói, yêu một người không hề yêu mình…. xét ra cũng hao hao như ngồi ở sân bay mà chờ tàu lửa.

Dĩ nhiên Alice và Bob mã hoá thư rồi mới gửi đi, mà lần này không chơi Caesar cipher nữa, bị Eve brute-force một lần nên tởn rồi. Họ dùng mật mã bất đối xứng, khoá công khai RSA.

Alice chọn cho mình hai số nguyên tố rất đẹp là p = 17 và q = 11. Sau đó, nàng ấy tính ra số N = p * q = 187. Tiếp tục, nàng thơ của Bob tính tiếp φ = (p-1) * (q-1) = 160. Nhắc đến phi ( φ ) là ghét ghét rồi. Rồi, nàng ấy lại ngồi chọn tiếp số e sao cho 1 < e < n và ước chung lớn nhất của e và φ là 1. Okie…. “Em sẽ chọn số 7 quyền lực và may mắn nhé anh, Bob”, Alice said. hahahahahahha…. Tới đây, Alice sẽ quăng về phía chàng Bob số n và số e, giữ lại cho mình số p và q làm private key. Nghĩa là, e và n trở thành public key ai lấy cũng được. Eve cũng sniff được dễ dàng, nhưng Eve không có nhu cầu gửi thư cho Alice. Eve chỉ muốn Alice rời xa Bob mà thôi.

Đến đây, anh Bob sẽ dùng public key để mã hoá thư của mình lại rồi gửi cho Alice. Bob tối nay hơi mệt, chỉ muốn ngủ sớm, nên gửi đơn giản một chữ ‘X’ tượng trưng cho nụ hôn mà thôi. X trong bảng ASCII có số DEX là 88. Bob sẽ áp dụng hàm công thức một chiều để tìm c. c sẽ bằng me mod n. Tức là c = 887mod 187 = 11. Sau đó, Bob lập tức gửi văn bản encrypted này cho Alice. Khốn khổ cho nàng Eve, với các hàm số mũ trong số học đồng dư là hàm một chiều, nàng có ngồi tính khờ luôn cũng chưa chắc dò ra được private key mà ả Alice đang nắm giữ. hiuhiu….

Thư C về tay Alice, và nàng ấy giải ra được, vì nàng nắm chắc p và q rồi. Nàng sẽ dùng công thức để tìm ra d. Ôi, cái giá trị d này làm tôi lao đao suốt cả một buổi chiều. Quá tốn thời gian luôn. Cho đến khi ngồi đọc một mớ page giải thích bằng tiếng Anh đại loại là xài Extended Euclidean algorithm (Thuật toán Euclide mở rộng) để tìm ra d. Và dĩ nhiên, một đứa dốt toán như tôi thì ngáo ngơ với cái thuật toán này luôn. Hồi xưa học mấy môn tự nhiên tệ lắm… ;___;

Nhưng may sao, lên youtube search thử thì có một video của chị kia bên nước ngoài giải tay và giải thích từng step by step nên hiểu ra được cái Euclide mở rộng đó áp dụng trong đây ra sao. À nói luôn, tôi cũng không hiểu 100% cái thuật toán Euclide đó đâu, chỉ hiểu đủ để áp dụng mà tìm ra d thôi.

Công thức tìm d hơi khác một xíu so với hình ở phía trên, nhưng thật ra chuyển đổi xíu thôi chứ không có gì sai biệt về tính chất cả.

e * d mod φ = 1

⇔ 7 * d mod 160 = 1

————————————–

160x + 7y = 1

160 = 10(7) + 90

7 = 0(90) + 7

90 = 10(7) + 20

7 = 0(20) + 7

20 = 2(7) + 6

7 = 1(6) + 1

————————————–

1 = 7 – 1(6)

1 = 7 – 1(20 – 2(7))

1 = 3(7) – 1(20)

1 = 3(7) – 1(90 – 10(70)

1 = 13(7) – 1(90)

1 = 13(7) – 1(160 – 10(7))

1 = 23(7) – 1(160)

Những cái số đi kèm với số đóng ngoặc là nhân đấy. Và tới đây hết triển được nữa rồi, nên dừng. Và nhờ tôi nghe được chút xíu tiếng Anh, nên mới lĩnh hội được hết cái ý của chị ấy nói trong video. Nếu số tự nhiên đi kèm với (7) chỗ này – tức là nhân với e đó – mà là số dương thì nó chính là số d cần tìm. Còn ngược lại, nếu nó là số âm, thì làm thêm một bước nhỏ là lấy φ – x = d. Số ‘x’ chính là số nhân với e trong mớ triển khai trên ở dòng cuối cùng , nếu là số âm.

Vậy thôi, nếu như trong bài này, thì là d = 23.

Tới đây, Alice có thể thế d vào công thức cuối cùng để đọc mật thư Bob lãng mạn gửi cho rồi.

m = cd mod n.

Trong bài này thì sẽ là

m = 1123 mod 187 = 88.

Đây là DEX của ký tự ‘X’ trong bảng ASCII đấy. Vậy là mở được thư, nàng Alice bẽn lẽn tủm tỉm cười một mình hạnh phúc, có biết đâu chàng Bob đã ngủ khò khò còn nàng Eve thì úp mặt vào gối nằm khóc thút thít vì không đọc được thư của đôi trai gái đó. =))))

VÕ TÌNH THƯƠNG

votinhthuong9@gmail.com

 

Advertisements