Alan Turing và máy Enigma

Alan Turing, một con người, một tính cách và một số phận

Alan Turing sinh ngày 23-6-1912 tại London, ông là một trong những nhà khoa học lớn bị lãng quên của thế kỷ XX, cho dù ông là cha đẻ của các máy tính, hay ít nhất cũng  là một phần lý thuyết của nó. Sự đóng góp to lớn của ông quyết định cho sự chiến thắng của phe Đồng Minh trong chiến tranh thế giới thứ 2 (theo vietsciences). Mặc dù trước công chúng Alan Turing có thể được coi như là một nhà khoa học xuất sắc, giúp quân đội đồng minh giải mã máy Enigma. Nhưng về cá tính, ông là một người nhút nhát, hay mắc cỡ và lập dị. Lúc còn học ở đại học Cambridge, Turing thường để tóc tai quần áo bê bối và không cạo râu, hơn nữa ông có thói quen đeo đồng hồ ở thắt lưng và đeo mặt nạ phòng độc khi đạp xe vì ông bị dị ứng với phấn hoa.

Và bởi vì luật pháp Anh lúc bây giờ không chấp nhận người đồng tính cho nên ông bị buộc hoặc phải tiêm hormone nữ (estrogen) hoặc là phải ngồi tù. Phải nói thêm là y học thời bây giờ tin rằng có thể điều chỉnh giới tính của con người bằng cách tiêm estrogen, và thời đó người ta xem đồng tính luyến ái là một bệnh cần được chữa trị và là một tội danh được xác định trong luật pháp Anh.

Tác dụng phụ của việc này khiến ngực ông phát triển như phụ nữ và khiến ông cảm thấy bị làm nhục, do vậy ông đã ăn một quả táo có tẩm cyanure để tự sát vào ngày 7 tháng 6 năm 1954. Mãi đến tận 2009, tức là 55 sau ngày ông mất, thủ tướng Anh Golden Brown mới thay mặt chính phủ Anh xin lỗi Alan Turing vì đã đối xử một cách không nhân đạo với nhà khoa học này. Tên ông cũng đã được đặt cho giải tưởng thường niên của Hiệp hội Khoa học máy tính Hoa Kỳ cho các cá nhân và tập thể có đóng góp quan trọng cho nghành khoa học máy tính từ năm 1966.

Giải mã máy Enigma và phát minh ra máy tính Bombe

Enigma là một loại máy cơ điện dùng để mã hóa thông tin được phát triển bởi một kỹ sư người Đức (Arthur Scherbius) vào cuối chiến tranh thế giới thứ nhất. Ban đầu nó được dùng trong mục đích thương mại nhưng sau đó được chính phủ và quân đội Đức Quốc Xã sử dụng. Và trong chiến tranh thế giới thứ thứ hai, hải quân Đức đã sớm sử dụng máy Enigma để cáo vị trí ném bom, sự di chuyển của đối phương  v.v cho các tàu ngầm của mình mà quân đồng minh không thể giải mã được. Và các máy mã hóa Enigma này đã giúp quân đội Đức dành nhiều chiến thắng trước quân đồng minh trên biển.

Năm 1938 trở về Anh sau khi hoàn thành chương trình PhD tại đại học Princeton tại Mỹ, Alan Turing đã giúp quân đội Anh phát triển máy tính cơ điện tử Bombe trong một nỗ lực nhằm giải mã những thông điệp bí mật của hải quân Đức. Mặc dù trước đó, vào năm 1932, ba nhà toán học người Ba Lan làm việc cho Cục Cơ Yếu Ba Lan (The Polish Cipher Bureau) đã tìm ra nguyên lý hoạt động của máy Enigma quân sự và tìm ra lỗ hỗng của máy Enigma dựa trên hai tài liệu của Đức và hai trang thông số thiết lập hàng ngày của máy Enigma từ tình báo Pháp hoạt động tại Đức.

Máy Enigma có một lỗ hổng đó chính là một ký tự sẽ không bao giờ được mã hóa thành chính nó. Và mỗi sáng vào lúc 6h, quân đội Đức lại phát đi một bảng báo cáo thời tiết (Wetterbericht), do vậy dựa vào cáo cáo thời tiết (theo một mẫu cố định) và cách vận hành của máy Enigma người ta có thể suy luận ra được cấu hình của máy Engima ngày hôm đó. Để đáp ứng cho yêu cầu giải mã thông điệp mã hóa một cách nhanh chóng, Turing đã thiết kế ra máy Bombe để tìm ra vị trí sắp đặt của các rotor trong khoảng 20 phút bằng cách thử tất cả 17,576 vị trí của 3 rotors và các cách nối mạch điện khác nhau (nói cách khác là brute force).

Xem thêm: http://www.youtube.com/watch?v=V4V2bpZlqx8

Máy tính thuở sơ khai và Turing Test

Công trình nghiên cứu quan trọng đầu tiên của ông có tên “On Computable Numbers, with an Application to the Entscheidungs problem” hoàn thành năm 1936. Bài viết  này là tiền đề cho cái gọi là “Turing machine”, máy Turing là một thiết bị xử lý các ký tự và có thể giả lập logic của tất cả các thuật toán. Nó là một thiết bị đọc, xóa, viết các ký hiệu trên dải băng (tape), máy Turing đơn giản này là tiền đề cho các máy tính kỹ thuật số về sau. Và cũng trong bài viết trên, khái niệm “software” cũng được đề xuất lần đầu tiên bởi Alan Turing.

Vào năm 1950, trong một bài luận khác “Computing Machinery and Intelligence”, Alan Turing đã đưa ra một phép thử nhằm kiểm tra trí thông của máy tính có tương đương hoặc không khác với con người hay không. Trong đó, 2 người và một máy tính giao tiếp (cách ly, thông qua màn hình và bàn phím) với nhau bằng ngôn ngữ tự nhiên, nếu như người tham gia không nhận ra được đâu là người và đâu là máy thì máy đó vượt qua bài kiểm tra.

Xem thêm: http://www.youtube.com/watch?v=E3keLeMwfHY

Về máy Enigma

Về cấu tạo thì máy Enigma có một bàn phím giống như máy đánh chữ, và nhiều rotor (3-5), mỗi rotor bao gồm 26 chữ cái từ A đến Z. Căn bản, máy tạo ra thực hiện một loại mã hóa đơn giản, đó là mã hóa thay thế (substitution cipher) được dùng từ tận thời Ceasar. Tức là khi người ta nhập vào một ký tự máy sẽ chuyển nó thành một ký tự khác, nhưng mỗi lần gõ sẽ sinh ra một chữ khác nhau bởi một rotor khác nhau (gõ vào một ký tự 4 lần khác nhau sẽ sinh ra 4 ký tự mã hóa khác nhau). Khi nhấn một ký tự thì các rotor sẽ quay và thay đổi vị trí, sẽ có một rotor thay đổi vị trí nhanh, một rotor thay đổi vị trí với tốc độ trung bình và một rotor thay đổi vị trí chậm. Về mặt ý tưởng nó giống như kim giây, kim phút và kim giờ trên đồng hồ. Và thông điệp được mã hóa sẽ được truyền đi qua radio hoặc bằng mã morse.

Và nhờ một chuỗi các rotor này khiến máy Enigma phức tạp và khó giải mã. Bởi vì khi thay đổi thứ tự của các rotor cũng sẽ thay đổi thông điệp được mã hóa. Các vận hành viên sẽ có 1 bộ 5 rotor và họ chọn ra 3 trong số 5 rotor để lắp vào máy, như vậy có 5x4x3 = 60 cách chọn rotor. Nếu như máy có 3 rotor, thì sẽ có 6 hoán vị khác nhau của 3 rotor. Và trước khi mã hóa và giải mã một thông điệp thì các rotor sẽ được cài đặt ở vị trí bất kỳ trong 26 vị trí chữ cái trên rotor, như vậy có tất cả 26x26x26 = 17576 vị trí ban đầu cho 3 rotor. Chưa kể, có một bảng gồm 26 lỗ cắm tương ứng với 26 chữ cái và 10 dây cắm đôi để kết hợp 2 chữ cái lại với nhau, và có 150,738,274,937,250 cách cắm dây khác nhau. Cuối cùng, chúng ta có  158 tỷ tỷ cấu hình ban đầu khác nhau cho máy Engima.

17576 x 6 x 60 x 150,738,274,937,250 =158,962,555,217,826,360,000 

Do vậy, muốn sử dụng 2 máy Enigma để trao đổi các thông điệp (mã hóa và giải mã) thì các máy này phải có cùng cấu hình. Và cấu hình của máy có thể được liệt kê trên một bảng in trên giấy, qui ước thay đổi cấu hình máy Enigma theo từng ngày. Cho nên người Đức rất tự tin vào kỹ thuật mã hóa của máy Engima và tin rằng không gì có thể bẻ gãy được nó, tuy nhiên nó vẫn có điểm yếu ở trên.

Xem thêm  http://www.youtube.com/watch?v=G2_Q9FoD-oQ

Tham khảo:

Alan Turing - Wikipedia 
Enigma Machine - Wikipedia
Bombe - Wikipedia
Alan Turing - Vietsciences
PM's apology to codebreaker Alan Turing: we were inhumane
Hóa giải Enigma