Mục lục bài họcĐang ở d02-b2
Error checking and encryption
Why errors happen
Data can be corrupted during transmission by interference, by loss of signal over long distances, or by a break in the connection. So every transmission needs a way to detect that something has changed.
Parity check
One bit of each byte is reserved as the parity bit. It is set so that the total number of $1$s is even (even parity) or odd (odd parity), as agreed in advance.
Using even parity, to send $1011001$ the sender counts four $1$s — already even — so the parity bit is $0$, giving $01011001$.
The receiver counts the $1$s. If the count no longer matches the agreed parity, an error is detected.
Its critical weakness: if two bits change, the number of $1$s keeps the same parity, so the error is not detected at all. In general, parity only catches an odd number of changed bits.
It also cannot say which bit is wrong, only that something is wrong.
Checksum
A value is calculated from the data before sending and transmitted with it. The receiver recalculates the value from the data it received and compares.
If the two values differ, the data was corrupted and is requested again. A checksum is more reliable than a parity check because it depends on all the data, not just a count of bits.
Echo check
The receiver sends the data back to the sender, which compares it with the original. If they differ, the data is sent again.
Its weaknesses are worth stating: it doubles the traffic, and if a difference is found there is no way to know whether the error happened on the way out or on the way back.
Check digit
An extra digit is calculated from all the other digits and added to the end of a number. It is used on barcodes, ISBNs and bank account numbers.
When the number is entered or scanned, the digit is recalculated and compared — catching mistyped digits and, importantly, transposed digits (two digits swapped), which is one of the commonest human errors.
Automatic Repeat reQuest
ARQ uses acknowledgements and a timeout:
- the sender transmits a packet and starts a timer;
- if the packet arrives correctly, the receiver sends a positive acknowledgement;
- if no acknowledgement arrives before the timer runs out, the sender resends the packet;
- this repeats until the packet is acknowledged or a maximum number of attempts is reached.
Note what makes it different from the methods above: those only detect errors, while ARQ also corrects the situation by resending.
Encryption
Encryption scrambles data using a key so that anyone intercepting it cannot understand it. Plaintext becomes ciphertext.
| symmetric | the same key encrypts and decrypts. Fast, but the key itself must somehow be sent securely — which is the whole problem |
| asymmetric | a public key encrypts and a different private key decrypts. The public key can be shared openly because it cannot decrypt; only the private key can, and it never leaves the owner |
Note carefully what encryption does not do: it does not stop data being intercepted or stolen. It only makes the stolen data meaningless to whoever takes it.
Vì sao có lỗi. Dữ liệu có thể bị hỏng trên đường truyền do nhiễu, do suy hao tín hiệu trên quãng dài, hoặc do đứt kết nối. Vì thế mọi đường truyền đều cần một cách phát hiện rằng có thứ gì đó đã bị thay đổi.
Kiểm tra chẵn lẻ. Một bit trong mỗi byte được dành làm bit chẵn lẻ. Nó được đặt sao cho tổng số bit $1$ là chẵn (chẵn lẻ chẵn) hoặc lẻ (chẵn lẻ lẻ), theo quy ước thống nhất trước.
Dùng chẵn lẻ chẵn: để gửi $1011001$, bên gửi đếm được bốn bit $1$ — đã chẵn — nên bit chẵn lẻ là $0$, cho ra $01011001$.
Bên nhận đếm lại số bit $1$. Nếu số đếm không còn khớp với quy ước, tức là có lỗi.
Điểm yếu chí mạng: nếu hai bit cùng bị đổi, tổng số bit $1$ vẫn giữ nguyên tính chẵn lẻ, nên lỗi hoàn toàn không bị phát hiện. Nói tổng quát, kiểm tra chẵn lẻ chỉ bắt được khi số bit bị đổi là lẻ.
Nó cũng không cho biết bit nào sai, chỉ báo rằng có gì đó sai.
Tổng kiểm tra. Một giá trị được tính ra từ dữ liệu trước khi gửi và được truyền kèm theo. Bên nhận tính lại giá trị đó từ dữ liệu nó nhận được rồi so sánh.
Nếu hai giá trị khác nhau thì dữ liệu đã bị hỏng và được yêu cầu gửi lại. Tổng kiểm tra đáng tin cậy hơn kiểm tra chẵn lẻ, vì nó phụ thuộc vào toàn bộ dữ liệu chứ không chỉ vào số lượng bit.
Kiểm tra dội. Bên nhận gửi ngược dữ liệu về cho bên gửi, và bên gửi so với bản gốc. Nếu khác nhau thì gửi lại.
Hai điểm yếu đáng nêu: nó làm lưu lượng tăng gấp đôi, và nếu phát hiện khác biệt thì không có cách nào biết lỗi xảy ra ở lượt đi hay ở lượt về.
Chữ số kiểm tra. Một chữ số phụ được tính từ tất cả các chữ số còn lại và thêm vào cuối một dãy số. Nó được dùng trên mã vạch, mã sách quốc tế và số tài khoản ngân hàng.
Khi dãy số được nhập hoặc quét, chữ số đó được tính lại và so sánh — bắt được lỗi gõ sai và, quan trọng hơn, lỗi đảo chỗ hai chữ số, vốn là một trong những lỗi con người hay mắc nhất.
Yêu cầu gửi lại tự động. Phương pháp này dùng tín hiệu báo nhận và một bộ đếm thời gian chờ:
- bên gửi truyền một gói và khởi động đồng hồ;
- nếu gói tới nơi nguyên vẹn, bên nhận gửi lại một tín hiệu báo nhận;
- nếu hết thời gian chờ mà không có báo nhận, bên gửi truyền lại gói đó;
- lặp lại cho tới khi có báo nhận hoặc đạt số lần thử tối đa.
Chú ý điều làm nó khác các phương pháp trên: những phương pháp kia chỉ phát hiện lỗi, còn phương pháp này còn khắc phục bằng cách gửi lại.
Mã hoá. Mã hoá xáo trộn dữ liệu bằng một khoá, để ai chặn được cũng không hiểu nội dung. Bản rõ trở thành bản mã.
- Mã hoá đối xứng — cùng một khoá dùng để mã hoá và giải mã. Nhanh, nhưng bản thân cái khoá lại phải được gửi đi một cách an toàn — mà đó chính là vấn đề ban đầu;
- Mã hoá bất đối xứng — một khoá công khai để mã hoá và một khoá riêng khác để giải mã. Khoá công khai chia sẻ thoải mái được vì nó không giải mã được; chỉ khoá riêng mới giải mã được, và nó không bao giờ rời khỏi chủ sở hữu.
Chú ý kỹ điều mã hoá không làm được: nó không ngăn dữ liệu bị chặn hay bị đánh cắp. Nó chỉ làm cho dữ liệu bị lấy trở nên vô nghĩa với kẻ lấy được.
Bên gửi dùng chẵn lẻ chẵn để gửi byte $01011001$. (a) Xác nhận bit chẵn lẻ được đặt đúng. (b) Chỉ ra điều gì xảy ra nếu một bit bị đổi trên đường. (c) Chỉ ra điều gì xảy ra nếu hai bit bị đổi, và nêu hệ quả.
(a) Xác nhận bit chẵn lẻ.
Đếm số bit $1$ trong $01011001$: các vị trí có bit $1$ là thứ hai, thứ tư, thứ năm và thứ tám — tổng cộng bốn bit $1$.
Bốn là số chẵn, nên byte này thoả quy ước chẵn lẻ chẵn ✓
(b) Nếu MỘT bit bị đổi.
Giả sử bit đầu tiên đổi từ $0$ thành $1$, cho $11011001$.
Bên nhận đếm được năm bit $1$ — số lẻ. Điều này không khớp với quy ước chẵn lẻ chẵn, nên bên nhận biết dữ liệu đã hỏng và yêu cầu gửi lại.
Lỗi được phát hiện thành công.
(c) Nếu HAI bit bị đổi.
Giả sử bit đầu tiên đổi từ $0$ thành $1$, và bit thứ hai đổi từ $1$ thành $0$, cho $10011001$.
Bên nhận đếm được: bit thứ nhất, thứ tư, thứ năm, thứ tám — vẫn là bốn bit $1$, vẫn chẵn.
Byte hoàn toàn khớp với quy ước, nên bên nhận kết luận dữ liệu nguyên vẹn và chấp nhận nó.
Lỗi lọt qua hoàn toàn mà không ai biết.
Vì sao điều này xảy ra. Mỗi lần một bit đổi, tính chẵn lẻ lật. Đổi một bit thì nó lật một lần nên khác đi và bị phát hiện. Đổi hai bit thì nó lật hai lần và quay về như cũ.
Nói tổng quát: kiểm tra chẵn lẻ chỉ bắt được khi số bit bị đổi là lẻ.
Hệ quả. Đây là hạn chế nghiêm trọng, vì nhiễu thường làm hỏng nhiều bit liền nhau chứ không chỉ một bit đơn lẻ.
Kiểm tra chẵn lẻ cũng không cho biết bit nào sai, chỉ báo có gì đó sai.
Vì thế các hệ thống thật dùng tổng kiểm tra — nó phụ thuộc vào toàn bộ dữ liệu nên đáng tin hơn nhiều — và kết hợp với yêu cầu gửi lại tự động để không chỉ phát hiện mà còn khắc phục.
Giải thích vì sao mã hoá đối xứng gặp một vấn đề cơ bản khi hai bên chưa từng liên lạc, và mã hoá bất đối xứng giải quyết nó thế nào. Nêu rõ điều mã hoá không làm được.
Vấn đề của mã hoá đối xứng.
Mã hoá đối xứng dùng cùng một khoá để mã hoá và giải mã. Nghĩa là bên nhận phải có đúng cái khoá đó mới đọc được.
Nhưng nếu hai bên chưa từng gặp nhau, làm sao gửi cái khoá đi?
- gửi khoá qua chính đường truyền đó → kẻ nghe lén chặn được khoá rồi giải mã mọi thứ về sau;
- mã hoá cái khoá trước khi gửi → lại cần một khoá khác để làm việc đó, và vấn đề lặp lại y nguyên.
Đây là một vòng luẩn quẩn: muốn trao đổi an toàn thì cần khoá chung, mà muốn có khoá chung thì đã phải có kênh an toàn.
Mã hoá bất đối xứng giải quyết thế nào.
Nó dùng hai khoá khác nhau, gắn với nhau về mặt toán học:
- khoá công khai — chỉ dùng để mã hoá;
- khoá riêng — chỉ dùng để giải mã.
Điểm mấu chốt: khoá công khai không giải mã được chính thứ nó vừa mã hoá. Vì thế người nhận có thể công bố khoá công khai cho cả thế giới mà không mất an toàn.
Ai muốn gửi tin thì lấy khoá công khai đó mã hoá. Chỉ người giữ khoá riêng mới mở được, và khoá riêng không bao giờ rời khỏi máy chủ sở hữu — nên không có gì để chặn.
Vòng luẩn quẩn được phá vỡ: không cần trao đổi bí mật nào trước.
Cái giá. Mã hoá bất đối xứng chậm hơn đối xứng nhiều. Trong thực tế, các hệ thống thường dùng bất đối xứng chỉ để trao đổi an toàn một khoá đối xứng, rồi dùng khoá đối xứng đó cho phần dữ liệu còn lại — kết hợp được cả sự an toàn lẫn tốc độ.
Điều mã hoá KHÔNG làm được. Nó không ngăn được dữ liệu bị chặn, bị sao chép hay bị đánh cắp.
Kẻ tấn công vẫn lấy được đúng những byte đó. Mã hoá chỉ đảm bảo rằng những byte ấy vô nghĩa với hắn.
Đây là điểm hay bị viết sai, và câu trả lời nói mã hoá “ngăn hacker lấy dữ liệu” là không chính xác.
Đọc xong rồi — làm thử ngay
Bài tập của chương Data Transmission gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.