30/09/2018, 17:03

Tản mạn về Mật mã hiện đại (part 1)

Bài viết được post tại đây: http://portal.daynhauhoc.com/p/tan-man-ve-mat-ma-hien-dai-part-1/

#Tản mạn về Mật mã hiện đại (part 1)

Mật mã là một vấn đề gắn liền với suốt chiều dài lịch sử của con người và có thể nói là mật mã học đã đặt nền móng cho ngành khoa học máy tính phát triển. Hôm nay mình viết bài này xin chia sẻ một số kiến thức về mật mã hiện đại mà mình góp nhặt được, hi vọng bài viết này sẽ có ích

Con người từng nghĩ ra đủ loại mã hoá, rồi cũng chính con người cũng tìm đủ mọi cách để giải nó, đó là một cuộc chiến tay đôi rất sòng phẳng giữa bên tạo mã và bên giải mã, trận thua đau đớn nhất của bên tạo mã là không làm sao giải quyết được khâu phân phối chìa khoá giải mã, bạn tưởng tượng 2 thằng An và Bình buộc phải gửi 1 bức thư qua 1 đứa bạn có tính hay soi mói đời tư người khác tên là Chiến (thường thì trong mật mã người ta hay quy ước 2 thằng trao đổi thông tin là Alice và Bob còn nghe lén là Eve). An cho bức thư vào một cái hòm khoá kín, nhiệm vụ khó nhất bây giờ là làm sao đưa được cái hòm cho thằng Bình, rồi phải tìm cách đưa cả chìa khoá nữa chứ, không thì làm sao ông Bình ổng mở được, mà lại không có cách nào chuyển đồ được ngoài qua tay thằng Chiến...Làm sao giờ ta? An nghĩ....bạn cũng nghĩ thử xem...hm...hm...... :smile:

Nghĩ ra chưa? Nếu bạn nghĩ ra rồi thì bạn rất thông minh đó , vì đây là ý tưởng mà bên tạo mã đã chờ từ rất lâu. Còn nếu bạn chưa nghĩ ra thì để mình giải thích nhé:


An là Alice còn Bình là Bob

Đầu tiên, An khoá cái hộp đó lại gửi cho Bình (tất nhiên là mọi hoạt động đều qua tay thằng Chiến hết), Bình sẽ làm gì đây, hehe, [spoiler]KHOÁ THÊM VÀO ĐÓ 1 Ổ KHOÁ NỮA![/spoiler] rồi gửi lại cho An, An sẽ mở khoá mà lúc đầu đã khoá, rồi gửi lại Bình, rồi Bình mở khoá còn lại bằng chìa khoá của mình vậy là xong. Ý tưởng khoá kép này là nền tảng tạo nên mật mã công khai, mã bất đối xứng được dùng rất nhiều ngay nay, tất nhiên là ý tưởng này còn sơ khai và cần nhiều thay đổi nữa để trở nên hiệu quả. Để toán học hoá ý tưởng thì các nhà khoa học sử dụng toán đồng dư để tạo ra hàm 1 chiều và nó là tiền thân của các hàm băm sau này, một ví dụ điển hình về hàm băm là mã md5, hiện nay đang được sử dụng rất nhiều. (hàm một chiều là hàm tạo ra mã thì dễ mà giải ngược lại thì cực khó)

Đến đây bạn có thể vỗ đùi:“Đó, đúng như mình nghĩ mà”, nhưng cũng có thể bạn đang nghĩ: “Haha, tôi còn ý tưởng nữa hay hơn nhiều”, đúng là có một ý tưởng nữa cũng rất hay, nó như sau:

Đơn giản là An sản xuất được 1 loại khoá bấm với một chìa khoá và rất nhiều ổ khoá giống hệt nhau, xong gửi cái ổ khoá đó cho tất cả mọi người, tất nhiên là gửi cả cho Bình, và rồi khi Bình hoặc bất kì ai muốn gửi thư cho An thì chỉ cần lấy cái khoá bấm đó bấm vào 1 cái hòm(trong hòm có bức thư cần gửi) xong gửi cho An, vì chìa khoá có mỗi An có nên việc trao đổi này là rất an toàn. (nếu vẫn không phải đáp án mà bạn nghĩ ra thì chia sẻ ở dưới nhá)


Khoá bấm là khoá kiểu này này

Về mặt ý tưởng thì ở thời đó nếu bạn nghĩ được đến đây đã đủ để tên bạn lưu danh sử sách rồi. Việc làm của bạn giờ chỉ là hiện thực hoá ý tưởng đó thành dạng toán học, cái chỉ là này cũng đã đủ để làm nhiều nhà khoa học thời đó mất ăn mất ngủ, nửa đêm vỗ gối nước mắt đầm đìa đó :, nhưng rồi cuối cùng một ngày đẹp dời 3 nhà khoa học dựa trên những ý tưởng này mà tạo nên được một loại mã hoá mới, cực mạnh, đó là mã RSA. Mã có hàm một chiều dựa trên sử dụng tích 2 số nguyên tố, điều này giải thích tại sao số nguyên tố được quan tâm rất nhiều, lâu lâu lại thấy có bạn đăng bài tập về số nguyên tố lên Dạy Nhậu Học để hỏi, mình từng nghĩ:" Cái số nguyên tố có thì cái gì hay đâu mà cứ bắt học nó làm quái gì nhỉ?", và cuối cùng mình cũng đã tìm ra câu trả lời. Bây giờ mà bạn tìm ra được một thuật toán phân tích một số thành tích 2 số nguyên tố với tốc độ nhanh gấp đôi hiện tại chẳng hạn, thì có thể bạn sẽ làm cả thế giới chao đảo ấy chứ (hư cấu chút ), vì mật mã hiện nay chủ yếu dựa theo cái mã RSA này.

Vậy thực sự thì mã RSA là như nào?


public key là chìa khoá công khai, private key là chìa khoá bí mật

Mỗi người sẽ có 2 chìa khoá mã hoá , 1 cái công khai, ai cũng có thể biết, 1 cái bí mật chỉ 1 người biết, khi An muốn gửi một bức thư cho Bình, An sẽ mã hoá bức thư đó theo mã hoá công khai của Bình, rồi gửi cho Bình (giai đoạn này giống như là bạn bấm cái khoá bấm vậy, bấm vào được mà đếch mở ra được ) , Bình sẽ dùng khoá chỉ mình Bình biết giải mã và vậy là xong. Đó là sức mạnh của mật mã không đồng bộ (người mã hoá được chưa chắc đã có khả năng giải mã). Mình chỉ dám nói sơ sơ như vậy thôi, còn chi tiết về mặt toán học thì bạn có thể google hoặc đọc thêm ở cuốn The code book (Simon Singh)

Thế tương lai ngành mật mã sẽ đi về đâu? Bên nào sẽ chiến thắng? Tạo mã hay giải mã? phần 2 của bài viết mình sẽ giúp các bạn phần nào trả lời được những câu hỏi này.

Bài viết này có tham khảo một số nội dung trong cuốn The code book (Simon Singh) và các tài liệu khác trên internet.


À một fun fact khá thú vị là Ian Fleming (người tạo ra James Bond - 007) cũng từng tham gia vào cuộc chiến tìm khoá mã này. Bạn biết giải pháp của ông là gì ông, không thèm giải toán gì sất, nhảy lên tàu người ta cướp khoá mã xong về :lol:

http://vietnamdefence.com/Home/tinhbaoanninh/chiendichtinhbao/Tinh-bao-dien-tu-Anh-Bi-mat--May-ma-Triton-tu-chiec-tau-ngam-Duc-6/20154/54407.vnd


Đây là website xem kích cỡ mã RSA mà các nước trên thế giới sử dụng
http://indutny.github.io/collect-certs/


Phần 2 ở đây: Tản mạn về Mật mã hiện đại (part 2)

Lê Đình Huy viết 19:11 ngày 30/09/2018

Hơi dài nhưng đọc hay tuyệt cú mèo . Hình ảnh minh họa dễ hiểu nữa

Thành Phạm viết 19:15 ngày 30/09/2018

, Em muốn viết dài nữa cơ nhưng mà sợ mọi người ngại đọc nên thôi rút bớt đi vậy

Lê Đình Huy viết 19:19 ngày 30/09/2018

, Em muốn viết dài nữa cơ nhưng mà sợ mọi người ngại đọc nên thôi rút bớt đi vậy

Cũng tốt, chia ra từng phần đọc cũng được, hay đó chứ

Minh Hoàng viết 19:18 ngày 30/09/2018

Cuốn của Simon Singh viết khá hay, tiếc là bạn không chia sẻ về các hệ mật cổ điển.
Hiện nay người ta đã tìm ra các thuật toán sub-exponential, nên RSA muốn an toàn thì họ sử dụng những số nguyên tố nhiều hơn 450 chữ số. Giờ có thêm hệ mật công khai elliptic curve crypto (EEC) nữa, khóa ngắn hơn nhưng độ phức tạp vẫn tương đương.

Thành Phạm viết 19:17 ngày 30/09/2018

Hiện nay người ta đã tìm ra các thuật toán sub-exponential, nên RSA muốn an toàn thì họ sử dụng những số nguyên tố nhiều hơn 450 chữ số. Giờ có thêm hệ mật công khai elliptic curve crypto (EEC) nữa, khóa ngắn hơn nhưng độ phức tạp vẫn tương đương.

Bên tạo mã đang thắng lớn đây
Em muốn lắm nhưng sợ viết dài mọi người không đọc thôi , part 2 em viết 1 tí về lượng tử, chắc part 3 sẽ ngược dòng về mã cổ điển

Nguyễn Trung Tín viết 19:11 ngày 30/09/2018

Hay quá, chờ đợi phần hai. Trong thời gian chờ đợi thì nghiên cứu cách giải mã RSA trong nửa nốt nhạc đồng thời tìm thuật toán phân tích một số thành hai số nguyên tố nhanh gấp 1000 lần hiện tại mới được.

Thành Phạm viết 19:08 ngày 30/09/2018

Nếu mà ra thì từ từ hẵng công bố, chỉ cho mình trước nhá, để mình hack pass mấy thằng bạn chơi

Nguyễn Trung Tín viết 19:03 ngày 30/09/2018

À mà có chỗ mình không hiểu, tại sao lại phân tích một số thành hai số nguyên tố nhỉ? Mình nghĩ là kiểm tra một số có phải là số nguyên tố không và tạo một số nguyên tố có chiều dài x chứ nhỉ?
Còn nếu muốn gửi một thông điệp tới một người không biết mình thì phải làm sao? Ví dụ giờ gửi tới một người ở tương lai chẳng hạn, người đó không có biết key gì hết.

Thành Phạm viết 19:09 ngày 30/09/2018

Nói chung thì mã RSA được tạo mã bằng cách tìm 2 số nguyên tố to to một tí xong nhân với nhau, và lấy cái tích đó làm khoá công khai (public key), còn 2 số nhân tử kia thì chỉ người tạo ra nó biết, và lấy nó làm khoá bí mật (private key) do đó nếu bạn làm được ngược lại được thì bạn phá được cái mã đó.

Muốn gửi đến một người nào đó trong trạng thái bảo mật cao nhất thì bạn phải có public key của người đó và người đó phải có private key cho cái public key đó. Nói hình tượng thì bạn phải có cái khoá bấm do người nhận tin “sản xuất” (và tất nhiên người nhận cũng phải chưa làm mất cái chìa khoá ở đâu đó)

Mình viết bài này không dám đi sâu về mặt toán học vì nó khá lằng nhằng. Nếu bạn muốn tìm hiểu sâu hơn thì có thể google hoặc đọc cuốn sách mình giới thiệu. Sách đó tên tiếng việt là Mật mã từ cổ điển đến lượng tử có bán trên mạng rất nhiều.

Nguyễn Trung Tín viết 19:11 ngày 30/09/2018

Vừa đọc RSA trên Wiki, thú vị thật. Khi nào có thời gian sẽ đọc cuốn sách bạn giới thiệu, biết đâu xuất thần nghĩ ra cách mã hóa tốt hơn hoặc cách giải mã các thuật toán mã hóa hiện tại thì sao, haha. Một lần nữa cảm ơn bài viết của bạn.

Thành Phạm viết 19:11 ngày 30/09/2018

Có thể lắm chứ đôi khi chỉ cần những liên tưởng/ý tưởng khá dễ hiểu như 2 ví dụ của An Bình Chiến ở trên mà làm thay đổi toàn bộ ngành khoa học mật mã

Minh Hoàng viết 19:12 ngày 30/09/2018

Mình nghĩ là nên viết thêm về cách sinh key của RSA.

Thành Phạm viết 19:16 ngày 30/09/2018

Chắc em sẽ viết một bài độc lập khác để viết chi tiết về toán trong RSA

Làm giàu, làm giàu, làm giàu..... viết 19:11 ngày 30/09/2018

vừa đọc vừa liên tưởng tới alan với chistopher gửi mã với nhau trong lớp. thật ra hồi nhỏ cũng chơi trò này, bàn với nhau ký tự này có key là gì rồi ngang nhiên gửi cho nhau trong lớp truyền qua tay nhiều đứa chả đứa nào hiểu thầy cô bắt cũng không sợ.

Thành Phạm viết 19:13 ngày 30/09/2018

vừa đọc vừa liên tưởng tới alan với chistopher gửi mã với nhau trong lớp. thật ra hồi nhỏ cũng chơi trò này, bàn với nhau ký tự này có key là gì rồi ngang nhiên gửi cho nhau trong lớp truyền qua tay nhiều đứa chả đứa nào hiểu thầy cô bắt cũng không sợ.

tại anh nhắc đến phim này làm em có hứng viết

Đức Hải viết 19:08 ngày 30/09/2018

[quote=“thanhmssl10, post:1, topic:6762”]
An sẽ mã hoá bức thư đó theo mã hoá công khai của Bình, rồi gửi cho Bình (giai đoạn này giống như là bạn bấm cái khoá bấm vậy, bấm vào được mà đếch mở ra được ) , Bình sẽ dùng khoá chỉ mình Bình biết giải mã và vậy là xong. Đó là sức mạnh của mật mã không đồng bộ (người mã hoá được chưa chắc đã có khả năng giải mã)
[/quote] - Mình chưa hiểu chỗ này cho lắm nếu AN đã mã hóa theo mã công khai của Bình thì An phải hiểu nội dung của cái mà mình mã hóa cho Bình hiểu chứ ???

Đức Hải viết 19:15 ngày 30/09/2018

Nói chung thì mã RSA được tạo mã bằng cách tìm 2 số nguyên tố to to một tí xong nhân với nhau, và lấy cái tích đó làm khoá công khai (public key), còn 2 số nhân tử kia thì chỉ người tạo ra nó biết, và lấy nó làm khoá bí mật (private key) do đó nếu bạn làm được ngược lại được thì bạn phá được cái mã đó.

Mình nghĩ số nguyên tố thì nó bị giới hạn bởi tính chất của nó nên dù có to lên bao nhiêu cũng bị khoanh vùng được vậy thì làm sao bảo đảm tính an toàn được nhỉ ???

Thành Phạm viết 19:20 ngày 30/09/2018

Mình chưa hiểu chỗ này cho lắm nếu AN đã mã hóa theo mã công khai của Bình thì An phải hiểu nội dung của cái mà mình mã hóa cho Bình hiểu chứ ???

Tức là lúc đầu An có một lá thư kiểu: “mai nhậu quán bà Lan nhá” thì rõ ràng An là người viết thư thì An phải biết nội dung thư rồi, nhưng khi đã cho vào hòm khoá lại bằng khoá bấm của Bình phân phát cho thì không thể nào mở ra đọc lại nữa vì chỉ có Bình có chìa khoá mở thôi.

Mình nghĩ số nguyên tố thì nó bị giới hạn bởi tính chất của nó nên dù có to lên bao nhiêu cũng bị khoanh vùng được vậy thì làm sao bảo đảm tính an toàn được nhỉ ???

Đúng là về lí thuyết thì Chắc chắn một mã RSA có mạnh đến đâu thì cũng có thể giải được nhưng vấn đề là thời gian bao lâu, ví dụ cái mật thư kia mà hơn nghìn năm sau mới giải xong thì lỡ mất buổi nhậu rồi còn đâu

Đức Hải viết 19:05 ngày 30/09/2018

tks rất nhiều, bài viết rất hay ^^

17XGOD viết 19:17 ngày 30/09/2018

Bài ni đọc hay quá

Bài liên quan
0