Công cụ mã hóa RSA đơn giản

Hôm tối thứ Bảy vừa qua, có người comment (bình luận) ở một video giải thích về thuật toán RSA của tôi trên kênh Youtube (cũng của tôi) luôn =))) Đại ý là hỏi xin source code chạy demo cho thuật toán mã hóa này. Chợt nhớ lại học kì vừa rồi, có một môn học cũng yêu cầu code phần mềm mã hóa RSA và RC4. Buồn thay, bao nhiêu là thứ dồn dập, cuối cùng phần cộng điểm đó tôi không có thời gian làm.

Chợt hôm nay có người hỏi về nó, lại đang trong tâm thế thư giãn giữa kì thi cuối kì hahaha… nên tôi quyết định viết luôn một cái đơn giản minh họa.

Đây chỉ là bài viết ghi chép lại những cái tủn mủn vụn vặt về ý tưởng và khó khăn trong lúc ngồi lên ý tưởng và code thôi, chứ không phải giải thích lại cách chạy của giải thuật này đâu. Nếu bạn muốn, có thể xem các video giải thích của tôi về nó: video 1video 2.

Bên cạnh đó, nếu thích đọc nhâm nhi cà phê tách trà thì có thể đọc bài viết này của tôi, khá dài vì chi tiết.

Người ta nói từ lúc nảy ra ý tưởng tới lúc cho ra sản phẩm là cả một giai đoạn thử thách. Điều này không sai. Càng làm mấy cái side project kiểu này, tôi càng nhận thấy khâu ý tưởng và lên kế hoạch các bước mới quan trọng như thế nào. Ngay từ đầu nếu không hoạch định đàng hoàng ra ý tưởng, không rõ được sơ đồ phát triển, cứ bạ đâu làm đó, viết tới đâu suy nghĩ tới đó, vừa code vừa sửa, vừa thêm thắt ý tưởng thêm, thật điên đầu. Nó cũng hao hao như việc xây một cái nhà mà cứ mô tả bằng miệng với nhau, chớ hề xài có lấy một cái bản vẽ vậy =)))

Cái công cụ này, về căn bản chỉ để minh họa giải thuật nó chạy thế nào ở mức cơ bản nhất, chứ đem đi xài thật thì không khả thi lắm. Tôi làm ra chỉ bám sát vào cái gọi là đơn giản nhất của nó, tức là sử dụng những số nguyên tố nhỏ nhỏ thôi, không có tới mức 2048 bit đâu.

Tôi code cái này hoàn toàn bằng C# thuần tay, không dùng tới thư viện hỗ trợ có sẵn.

Ai cũng bảo Java lập trình “đã” hơn. Tạm thời lúc này tôi chưa biết nó “đã” như thế nào, nhưng quen với C# và IDE Visual Studio lắm rồi, nên chưa có nhu cầu.

Bước đầu tiên là hoạch định ra sơ sơ các bước phải làm trong đầu:

– Phải có hai số p và q đầu vào.

– Liệu tôi nên để người dùng tự chọn số e hay là để giải thuật lựa chọn số e cho đúng điều kiện của thuật toán? Sau khi cân nhắc, tôi quyết định để máy tính lựa chọn cho an toàn.

– Tính toán được các giá trị N, Φ và quan trọng là phải tìm ra số d. Không tìm được coi như bế tắc chỗ này.

Tạm thời là nhiêu đó cái cần xử lý, các phần còn lại từ từ tính sau. Trong tất cả những đầu vào kể trên, mỗi cái đều có cái hay cái dở lúc xử lý. Hai số p và q đầu vào, phải đảm bảo là chúng đều là số nguyên tố (chỉ chia hết cho 1 và chính nó). Tôi code tay một cái hàm nhỏ kiểm tra một số bất kỳ có phải là số nguyên tố hay không, sau đó check giá trị p và q.

Tiếp tục, tính giá trị N, Φ thì đơn giản rồi. Tiếp tục là giá trị e. Số e này phải đảm bảo được 2 điều kiện là nhỏ hơn N và GCD(e,Φ) phải bằng 1. GCD() là hàm tìm ước chung lớn nhất. Để lựa ra được giá trị phù hợp, tôi quyết định cho chạy một phát từ 1 tới 1000 và tìm ra xem trong dãy đó có bao nhiêu số nguyên tố. Tiếp tục, lấy các số nguyên tố đó kiểm tra xem GCD của nó và Φ có bằng 1 hay không. Nếu tìm ra được giá trị thỏa mãn điều kiện đó thì ghi nhận lại và dừng vòng lặp.

Lúc đầu tôi cho chạy ngược từ 1000 về 1 mới ghê haha =))) Giá trị e nó phù hợp đa phần là 997 thôi nhưng vì cảm thấy lớn quá, trong khi thống nhất ngay từ đầu chỉ demo với các số nguyên tố nhỏ, nên tôi cho chạy vòng lặp ngược lại.

Cũng nhờ vụ này mà biết tới vụ <tên_mảng>.Reverse<kiểu_dữ_liệu>() khi bỏ trong vòng lặp foreach. Thật tuyệt vời !

Tới lúc tìm giá trị d mới tốn thời gian. Lúc học lý thuyết cũng như giải bài tập tìm d là tôi được học cách dùng giải thuật Euclidean mở rộng (Extended Euclidean Algorithm) để giải quyết vấn đề. Giải tay cái này thì thấy cũng mơ hồ về mã giả rồi, tới lúc bắt tay vào code, thì thôi nghỉ =)))) Không code ra được.

Sau một đêm ngủ trằn trọc, sáng ra miệt mài…search hướng giải quyết tiếp thì may sao tìm ra được một cách giải quyết cực kỳ nhanh gọn. Tua tới đoạn 9:18 để xem cách tìm d nhanh chóng. Nói thật cả video đó tôi chưa có xem hết, cũng không cần xem làm gì, vì nếu xem rồi code y chang hướng đó thì còn gì là sản phẩm tự làm nữa. Tham khảo chỗ tìm d thôi rồi tự làm tiếp.

Tiếp tục tới phần mã hóa thông điệp. Nếu đã hiểu vấn đề, thì không chỉ mã hóa đơn thuần một chuỗi ký tự như trong bài này, mà có thể mã hóa để tạo chữ ký số các kiểu cho tập tin như docx, pdf, excel, image,… Không gì là không thể.

Lúc đầu tôi dùng double để lưu giá trị, nhưng lại xảy ra vấn đề với hàm mũ. Giá trị mã hóa đem đi giải mã, không trả về giá trị gốc. Sau khi lên Stackoverflow hỏi thử, may mắn đã có người giải thích giúp.

Có một vấn đề gây lỗi dai dẳng suốt 3 tiếng mà tôi không để ý. Sau khi giải quyết xong câu chuyện giới hạn của biến số bằng cách dùng BigInteger thì lại nảy sinh tiếp câu chuyện giá trị mã hóa không đúng với một câu dài. Nếu từng chữ cái (character) thì ok, không sao. Nhưng với kiểu string thì nó sẽ mã hóa tầm bậy.

Chỗ này là do lỗi ngu mất căn bản =)))

Tôi duyệt từng chữ cái trong chuỗi và đem đi mã hóa. Ok, bước này không có vấn đề. Vấn đề nằm ở cách tôi lưu lại giá trị mã hóa. Thay vì lưu trữ từng giá trị thu được, tôi lại đi… cộng dồn chúng!

Lầm lẫn giữa phép gán “=” và phép cộng dồn “+=” khiến câu chuyện đi theo một hướng căng thẳng.

Cách giải quyết là sau khi mã hóa xong, ta lấy giá trị decimal thu được ép kiểu thành character để thu được chuỗi mã hóa. Và tương tự như ý tưởng đó cho cách giải mã.

Khi gặp chỗ bí trong lúc code, tôi giải quyết bằng cách cắt ra từng phần nhỏ, đem giải quyết thật triệt để trong một project khác rồi ghép lại thành một phần tổng thể. Chính nhờ thế mà side project lần này hoàn thành sớm trong một ngày.

Simple RSA - Console.jpg

Bằng cách đưa qua console để giải quyết…

Simple RSA - Windows Form.jpg

Và chỉnh sửa thành sản phẩm hoàn thiện mong muốn.

Code tôi sẽ public trên Github của tôi, sau khi tôi chỉnh sửa lại một lần nữa và comment code cẩn thận, cũng như lọc bớt đi các phần dư thừa trong quá trình làm. Đặc trưng của tôi là tôi không xóa đi các code cũ, mà khóa chúng lại bằng comment để phòng trường hợp cần đọc lại.

Video minh họa cho bài viết này: https://youtu.be/2vAu7HU5zyI.

Ngày chủ nhật đầu tiên của năm 2018 kết thúc với một sản phẩm công cụ mã hóa RSA.

VÕ TÌNH THƯƠNG

votinhthuong9@gmail.com

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s