Ba ng chư ca i trong mã hóa chuỗi

Question

Ở mật mã một bảng thế, ta có ánh xạ 1-1 giữa các ký tự trong bản rõ và bản mã. Khóa của mật mã 1 bảng thế chính là thứ tự sắp xếp giữa các ký tự trong bản rõ và bản mã tương ứng.

Trong mật mã đa bảng thế, ta sử dụng nhiều bảng thế khác nhau theo một thứ tự xác định. Ánh xạ giữa bản rõ và bản mã là Một – Nhiều. Khóa của mật mã nhiều bản thế ngoài các bản thế được sử dụng còn cần thêm thông tin về thứ tự sử dụng các bản thế đó.

Xét một hệ mã đơn giản với bảng chữ gồm 4 chữ cái {a,b,c,d} Giả sử tần xuất xuất hiện của mỗi chữ trong ngôn ngữ như sau: Pa = 0.5, Pb =0.05, Pc = 0.2, Pd = 0.25 Ta dùng hai bảng thế và một chuỗi khóa để quyết định thứ tự hòa trộn hai bảng thế này. Bảng thế 1:

Mã:

[INDENT=3]a b c d
B D A C
[/INDENT]

Bảng thế 2:

Mã:

[INDENT=3]a b c d
D B C D
[/INDENT]

Tạo mã bằng phương pháp trộn 2 bảng thế theo khóa “12”

Mã:

[INDENT]X : aba cada da ca baa
Z : 121 2121 21 21 212
Y : BBB CBAB AB CB BBD
[/INDENT]

Ở ví dụ trên người ta đã hoà trộn hai bảng thế liên tục kế tiếp nhau. Nhờ đó phân bố tần xuất xuất hiện của các chữ mã sẽ bị thay đổi so với tin và bằng phẳng hơn.

Mật mã Vigenère

Mật mã Vigenère là một phương pháp mã hóa văn bản bằng cách sử dụng xen kẽ một số phép mã hóa Caesar khác nhau dựa trên các chữ cái của một từ khóa. Nó là một dạng đơn giản của mật mã thay thế dùng nhiều bảng chữ cái.

Mã hoá là phương pháp để biến thông tin (hình ảnh, văn bản) từ định dạng bình thường sang dạng thông tin mà chúng ta không thể hiểu được nếu không có phương tiện giải mã. Đồng thời, mã hoá có vai trò quan trọng trong giao dịch điện tử để đảm bảo độ bảo mật, toàn vẹn của thông tin khi truyền trên mạng. Thông thường, mã hóa được áp dụng nhiều trong các ví điện tử quen thuộc với chúng ta như Momo, Zalopay, Shopee Pay….Trái lại, giải mã là quá trình ngược của mã hoá, biến thông tin từ dạng được mã hoá về dạng thông tin ban đầu.

Mật mã Caesar là một dạng mật mã thay thế, trong đó mỗi ký tự ở văn bản ban đầu sẽ được thay thế bằng một ký tự khác, có vị trí cách nó một khoảng xác định trong bảng chữ cái. Cũng giống như các loại mật mã thay thế khác, mật mã Caesar rất dễ bị phá giải. Tuy nhiên đây là một bài toán hay để chúng ta áp dụng kiến thức đã học về “vòng lặp” và “mảng” ở bài 3 của khoá CS 101. Hãy thử tưởng tượng các bạn muốn kể một câu chuyện bí mật cho người bạn thân của mình. Để bảo mật câu chuyện riêng tư không bị lộ ra ngoài, chúng ta cần mã hóa câu chuyện và gửi cho bạn mình kèm với phương pháp giải mã. Cách làm này hết sức thú vị phải không nào!

Người đã sáng chế ra cách mã hóa Caesar thú vị là vị hoàng đế Julius Caesar. Kỹ thuật này đã được phát triển vào khoảng năm 100 Trước Công nguyên. Hoàng đế Caesar đã dùng nó để gửi những mệnh lệnh quan trọng cho những tướng sĩ trên chiến trường. Do đó, nếu bọn giặc có bắt được người truyền tin thì cũng không thể đọc và hiểu được nội dung của bức thư mã hóa đó. Kiến thức này thật sự rất hữu ích và được áp dụng cho tới ngày hôm nay.

Kiến thức lập trình:

Một số kiến thức chúng ta đã được học ở bài 3 của khoá CS 101 sẽ được áp dụng để hoàn thành chương trình mã hoá này:

Mảng và cách lấy phần tử của mảng trong Python.
Vòng lặp for và while trong Python.
Câu lệnh input() để nhập dữ liệu trong Python.
Câu lệnh print() để in thông báo ra màn hình.
Kiểu dữ liệu boolean trong Python với so sánh ==.
Bài toán:

Chúng ta sẽ sử dụng Thonny để xây dựng một chương trình vừa giúp mã hoá, vừa giúp giải mã Caesar. Chương trình sẽ cho người dùng nhập một câu muốn mã hoá và số ký tự muốn dịch chuyển trong bảng chữ cái (k). Số k dương sẽ dịch chuyển văn bản sang phải (theo thứ tự từ A sang Z). Số k âm sẽ dịch chuyển văn bản sang trái (theo thứ tự từ Z sang A).

Ví dụ 1:

Văn bản gốc (Văn bản chưa mã hóa): ABCDEF

Văn bản mã hóa: CDEFGH

Trong ví dụ trên, các kí tự trong văn bản gốc được mã hóa bằng cách dịch sang phải 2 kí tự. k=2.

GốcABCDEF…XYZMã hóaCDEFGH…ZAB

Vì được dịch sang phải 2 ký tự nên A được mã hóa thành C, B mã hóa thành D… Đặc biệt, Y được mã hóa thành A, Z được mã hóa thành B, quay lại các ký tự đầu tiên.

Ví dụ 2:

Văn bản gốc (Văn bản chưa mã hóa): ABCDEF

Văn bản mã hóa: YZABCD

Trong ví dụ trên, các kí tự trong văn bản gốc được mã hóa bằng cách dịch sang trái 2 kí tự. k=-2.

GốcABCDEF…XYZMã hóaYZABCD…UVX

Vì được dịch sang trái 2 ký tự nên C được mã hóa thành A, D mã hóa thành B… Đặc biệt, A được mã hóa thành Y, B được mã hóa thành Z, quay lại các ký tự cuối cùng.

Chúng ta có thể thấy rằng k âm là phương pháp giải mã cho mã hoá với k dương và ngược lại.

Trước khi bắt tay vào lập trình, chúng ta có thể thử chương trình để mã hoá và giải mã Caesar: https://s4v.trinket.io/sites/caesar

Bắt tay vào lập trình thôi nào!!!

Thuật toán

Trước khi bắt tay vào viết code, chúng ta sẽ cùng suy nghĩ một thuật toán để giải quyết bài toán này nhé. Chúng ta có thể biểu diễn tất cả các ký tự trong bảng chữ cái bằng một mảng trong Python.

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']

Mảng arr có 26 phần tử. Với một ký tự bất kỳ, chúng ta có thể tìm được vị trí (index) i của nó trong mảng. Do đó khi dịch chuyển ký tự đó sang phải k kí tự, vị trí mới sẽ là i + k. Nếu dịch chuyển ký tự đó sang trái k kí tự thì khi đó k < 0 nên vị trí mới vẫn sẽ là i + k.

Trong trường hợp chúng ta dịch chuyển qua hai đầu của bảng chữ cái thì sao nhỉ? Ví dụ: Ký tự ‘X’ ở vị trí 23 trong mảng. Khi dịch chuyển sang phải 3 ký tự, vị trí mới sẽ là 23 + 3 = 26. Tuy nhiên vị trí cuối cùng của mảng arr là 25. Do đó, chúng ta phải quay lại vị trí đầu tiên (0) của ký tự ‘A’. Trong trường hợp này, khi dịch chuyển, chúng ta đã đi hết 1 lượt mảng arr. Chúng ta có thể thấy công thức tính vị trí sau khi dịch chuyển là 23 + 3 – 26 * 1 = 0.

Lấy một ví dụ khác: Ký tự ‘X’ ở vị trí 23 trong mảng. Khi dịch chuyển sang trái 80 ký tự, vị trí mới sẽ là 23 – 80 = -57. Từ vị trí ký tự ‘X’, nếu dịch sang trái 23 ký tự, chúng ta sẽ đến vị trí của ký tự ‘A’. Như vậy, chúng ta đã đi hết 1 lượt mảng arr. Từ vị trí ký tự ‘A’, dịch tiếp sang trái 26 ký tự, chúng ta sẽ đi hết một lượt nữa mảng arr và quay lại vị trí ký tự ‘A’. Tiếp tục dịch sang trái 26 ký tự, chúng ta sẽ tiếp tục đi hết một lượt nữa mảng arr và quay lại vị trí ký tự ‘A’. Chúng ta còn phải dịch sang trái 5 ký tự nữa. Như vậy chúng ta sẽ đến vị trí ký tự ‘V’. Tóm lại, chúng ta đã đi hết 3 lượt mảng arr. Chúng ta có thể thấy công thức tính vị trí sau khi dịch chuyển là 23 – 80 + 26 * 3 = 21.

Để tính xem phải đi qua mảng arr bao nhiêu lần, chúng ta có thể sử dụng phép toán floor division trong Python. Floor division trong Python là //. Floor division sẽ trả về số nguyên lớn nhất bé hơn kết quả của phép chia thông thường. Ví dụ: Với phép chia thông thường, chúng ta có 3 / 2 = 1,5. Tuy nhiên với floor division, 3 // 2 = 1, bởi vì 1 là số nguyên lớn nhất bé hơn 1,5. Lấy một ví dụ khác: Với phép chia thông thường, -57 / 26 = -2,19. Tuy nhiên với floor division, -57 // 26 = -3, bởi vì -3 là số nguyên lớn nhất bé hơn -2,19.

Tổng kết lại, nếu chúng ta ở vị trí i trong mảng arr và chúng ta dịch k ký tự, công thức tính vị trí sau khi dịch chuyển là i + k – 26 * ((i + k) // 26).

Code:

Bước 1: Viết các câu lệnh khai báo cần thiết

Chúng ta sử dụng câu lệnh input() để hỏi người dùng khi nào muốn dừng trò chơi và vòng lặp while để tiếp tục trò chơi tương tự như trò chơi Nhà thám hiểm và cánh cửa bí mật ở bài 2. Chúng ta cũng tạo mảng arr để lưu bảng chữ cái:

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
tiep = 'y'
while tiep == 'y':
    tiep = input('Nhập y để tiếp tục hoặc n để thoát: ')

Trong vòng lặp while, chúng ta sẽ sử dụng câu lệnh input()để yêu cầu người dùng nhập câu cần mã hóa và số ký tự muốn dịch chuyển. Chúng ta cần tạo biến để lưu chuỗi sau khi được mã hoá:

plaintext = str(input("Bạn hãy nhập câu muốn mã hoá: ")).upper()
jump = int(input("Bạn muốn dịch sang mấy ký tự? "))
t = ''

Để đơn giản, chúng ta sẽ sử dụng câu lệnh .upper() để in hoa tất cả các ký tự trong câu người dùng nhập vào. Code hoàn chỉnh sẽ là:

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
tiep = 'y'
while tiep == 'y':
    plaintext = str(input("Bạn hãy nhập câu muốn mã hoá: ")).upper()
    jump = int(input("Bạn muốn dịch sang mấy ký tự? "))
    t = ''
    tiep = input('Nhập y để tiếp tục hoặc n để thoát: ')

Bước 2: Xác định vị trí của ký tự trong mảng arr:

Một câu được biểu diễn bằng kiểu dữ liệu chuỗi (string) trong Python. Chúng ta đã được học ở bài 3, một chuỗi là một mảng mà phần tử là các ký tự trong chuỗi. Ví dụ: chuỗi “STEAM” là một mảng gồm 5 phần tử “S”, “T”, “E”, “A”, “M”. Như vậy để lấy các ký tự từ chuỗi, chúng ta có thể sử dụng vòng lặp for:

for character in plaintext:
    print(character)

Chúng ta có thể sử dụng câu lệnh print để debug. Trong vòng lặp for, để lấy ra vị trí của ký tự ở trong mảng arr, chúng ta sử dụng thêm vòng lặp while với biến i để lưu vị trí của ký tự trong mảng. Biến i bắt đầu từ 0 và sẽ được cập nhật trong vòng lặp để đi đến vị trí mới trong mảng arr. Chúng ta sử dụng câu lệnh if để kiểm tra xem phần tử ở vị trí i trong mảng arr có giống với ký tự trong chuỗi không. Nếu giống, chúng ta sẽ break. Chúng ta vẫn có thể sử dụng câu lệnh print để debug:

i = 0
while i < len(arr):
    if character == arr[i]:
        print('Giống')
        break          
    i = i + 1

Code hoàn chỉnh sẽ là:

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
tiep = 'y'
while tiep == 'y':
    plaintext = str(input("Bạn hãy nhập câu muốn mã hoá: ")).upper()
    jump = int(input("Bạn muốn dịch sang mấy ký tự? "))
    t = ''
    for character in plaintext:
        i = 0
        while i < len(arr):
            if character == arr[i]:
                print('Giống')
                break          
            i = i + 1
    tiep = input('Nhập y để tiếp tục hoặc n để thoát: ')

Bước 3: Mã hoá ký tự:

Sau khi xác định được vị trí i của một ký tự trong chuỗi, chúng ta sẽ sử dụng công thức tìm vị trí mới ở trong phần thuật toán để xác định ký tự sau khi mã hoá:

character_code = arr[i + jump - len(arr) * ((i + jump) // len(arr))]

Ngoài ra, chúng ta sẽ thêm một trường hợp. Nếu ký tự là khoảng trắng thì ký tự sau khi mã hoá cũng sẽ là khoảng trắng:

 elif character == ' ':
    character_code = ' '

Code hoàn chỉnh sẽ là:

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
tiep = 'y'
while tiep == 'y':
    plaintext = str(input("Bạn hãy nhập câu muốn mã hoá: ")).upper()
    jump = int(input("Bạn muốn dịch sang mấy ký tự? "))
    t = ''
    for character in plaintext:
        i = 0
        while i < len(arr):
            if character == arr[i]:
               character_code = arr[i + jump - len(arr) * ((i + jump) // len(arr))]
               break
            elif character == ' ':
               character_code = ' '          
            i = i + 1
    tiep = input('Nhập y để tiếp tục hoặc n để thoát: ')

Bước 4: Kết nối các ký tự sau khi mã hoá thành chuỗi:

Các ký tự trong chuỗi có thể được xem như một chuỗi con. Để kết nối hai chuỗi thành một chuỗi, chúng ta sử dụng +:

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
tiep = 'y'
while tiep == 'y':
    tiep = input('Nhập y để tiếp tục hoặc n để thoát: ')

0

Ở bước 1, chúng ta đã sử dụng biến t để lưu câu sau khi được mã hoá. Cuối cùng, chúng ta sẽ in ra câu sau khi được mã hoá:

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
tiep = 'y'
while tiep == 'y':
    tiep = input('Nhập y để tiếp tục hoặc n để thoát: ')

1

Chúng ta sử dụng %s để thêm vào một biến có kiểu dữ liệu chuỗi vào câu lệnh print. Ngoài ra chúng ta sẽ thêm % cùng với tên biến.

5. Tada!!!

Như vậy, các bạn học sinh đã hoàn thành xong game giúp mã hoá và giải mã Caesar nhanh chóng rồi đấy. Tuy quá trình làm game không ít khó khăn nhưng chắc chắn thành quả của các bạn rất hữu ích để áp dụng ngay trong cuộc sống. Chúng ta hoàn toàn có thể sử dụng chương trình này để mã hoá ngay một câu đố và đem cho mọi người đau đầu giải mã.

Chương trình Python hoàn chỉnh của game sẽ là:

arr = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
tiep = 'y'
while tiep == 'y':
    tiep = input('Nhập y để tiếp tục hoặc n để thoát: ')

2

Có rất nhiều cách chúng ta có thể cải tiến game này. Các bạn hãy nghĩ một cách nào đó chúng ta có thể loại bỏ vòng lặp while sử dụng để đi qua các phần tử trong mảng arr. Ngoài ra, các bạn có thể cải tiến game bằng cách mã hoá cả chữ hoa và chữ thường, chứ không cần phải chuyển hết sang chữ hoa.

Không chỉ vậy, thầy Harry và thầy Đức có một gợi ý hữu ích cho các bạn học sinh. Nếu chúng ta còn nhớ trong bài Vui học cùng thầy cô 1, thầy Đức đã giới thiệu cho chúng ta bảng mã ASCII. Trong bảng mã ASCII cũng có hai bảng chữ cái in hoa và in thường đấy. Chúng ta có thể chuyển một ký tự sang mã ASCII bằng câu lệnh ord() và chuyển từ mã ASCII về lại ký tự bằng câu lệnh chr(). Sau đó, chúng ta có thể chuyển từ số trong bảng mã ASCII thành vị trí của một phần tử trong mảng arr. Các bạn hãy cùng thử nhé!

Một gợi ý nữa để cải tiến game đó là chúng ta có thể sử dụng phép toán % trong Python để tính số lần chúng ta đi hết mảng arr. Phép toán này giúp chúng ta tìm số dư trong một phép chia. Ví dụ: 3 % 2 = 1.

Nhờ áp dụng ngay kiến thức của bài 3 khoá CS 101, bạn Đức Hoàng đã tạo ra được game “Mã hóa Caesar” hết sức thú vị và thực tế. Các bạn học sinh cũng hãy thử bắt tay vào sáng tạo một game cho riêng mình nhé! Sau khi hoàn thành game, các bạn có thể chia sẻ game của mình trên STEAMese Profile.

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

mẹo hay Caesar code tool Mật mã học

Ba ng chư ca i trong mã hóa chuỗi

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội