Các câu hỏi phỏng vấn [16]
Ngô Quang Hưng | 19 tháng 06, 2006 | 
Bản để in
- Cho số thực
bất kỳ, chứng minh rằng trong dãy số 
có ít nhất một số nằm trong khoảng 
của một số nguyên.
- Tuyết bắt đầu rơi trước nửa đêm. Đến nửa đêm có một xe ủi tuyết đi ủi trên đường. Xe đi được một dặm trong 1 giờ đầu tiên, và 1/2 dặm trong giờ thứ hai. Tuyết bắt đầu rơi từ khi nào? (Giả sử xe ủi đi với tốc độ tỉ lệ nghịch với chiều cao của tuyết.)
- An cần gửi một nhẫn kim cương cho Bình. An và Bình mỗi đứa có vài cái khóa cùng chìa cho chúng (mỗi khóa một chìa). An có một cái hộp thừa lớn để bỏ nhẫn vào. Hộp có móc tròn khá lớn để tròng khóa vào. Làm thế nào để An gửi nhẫn cho Bình một cách bảo đảm?
Anh Hưng mô tả kỹ hơn câu số 48 được không ạ? Nghĩa là chìa khóa của An có mở được khóa của Bình (và ngược lại) không? Cái hộp có đủ để bỏ 1 số chìa hoặc khóa vào đó ko?
Em nghĩ bài này không khó. Chỉ việc áp dụng một security protocol đơn giản. Nhưng em muốn hiểu rõ bài toán để xem nên áp dụng symmetric hay asymetric protocol :-).
Không, mỗi khóa chỉ có một chìa.
Em ko hiểu như thế nào thì gọi là bảo đảm? Làm thế này có đc ko ạ
+) An gửi cái hộp kèm theo 1 cái khóa (ko kèm chìa) cho Bình
+) Bình nhận đc, bỏ 1 cái khóa (ko kèm chìa) vào trong hộp và dùng khóa của An để khóa hộp lại, sau đó gửi lại cho An.
+) An mở khóa (vì cái khóa dùng để khóa hộp là khóa của An) rồi cho nhẫn vào hộp, dùng khóa của Bình gửi để khóa hộp, gửi sang cho Bình.
+) Bình lôi chìa khóa của mình ra rung đùi mở hộp lấy nhẫn ra đeo
Cai’ nay` co’ phai ung dung mot “public key encryption scheme” khong anh Hung? Em thay Mg9H tra loi cung duoc, nhung neu co mot nguoi nua o giua An va Binh thi cach cua Mg9H coi nhu thua ?
Ừ, cách của Mg9H cũng được. Nếu làm thế thì có lẽ đơn giản nhất là cho Bình gửi khóa (của Bình) cho An. An dùng khóa đó khóa hộp nhẫn gửi cho Bình. Nghĩa là An không cần khóa hay chìa, đúng kiểu PKE như Jalfal nói.
Lúc đầu tôi định đố theo hướng khác, nhưng câu này có lẽ chỉ đến vậy mà thôi.
47. Tuyết rơi ~46ph trước nửa đêm.
Gọi a0 là chiều dày mà tuyết rơi thêm đc trong 1h
a là chiều dày tuyết lúc nửa đêm
=> Thời gian tính từ khi tuyết bắt đầu rơi đến nửa đêm: a/a0
Chiều cao của tuyết:
Lúc nửa đêm: a =>vận tốc xe v1
1h: a+a0 => v2
2h: a+2*a0 => v3
Vi vận tốc xe tỷ lệ nghịch với chiều dày tuyết nên ta có:
a*v1=(a+v0)*v2=(a+2*a0)*v3
Từ đó suy ra:
a/a0= v2/(v1-v2) (1)
a/a0= (2*v3)/(v1-v3) (2)
Mặt khác, ta có: v1+v2=2*(v2+v3) => v1=v2+2*v3 (3)
Thay (3) vào (1), (2):
a/a0= v2/(2*v3) (1′)
a/a0= (2*v3)/(v2+v3) (2′)
như vậy ta chỉ cần tìm tỷ số v2 và v3 sẽ đc a/a0
Từ (1′) và (2′) ta đưa đc về phương trình đẳng cấp bậc 2 của v2 và v3.
Đặt v3=k*v2
Giải tính đc: k=(1+sqrt(17))/8
=>a/a0 = 4/(1+sqrt(17)) ~ 46 phút.
Hix, viết dài dòng thật, ko biết có làm nhầm chỗ nào ko
Anh Hưng, em nghĩ giải pháp cho câu 48 chưa thuyết phục lắm. Vấn đề ở đây là ta đang giả sử có 1 người trung gian đang muốn lấy chiếc nhẫn, nhưng bắt buộc phải gửi cái hộp đi. Ta tạm gọi người này là MIT (Man-in-the-middle). Như thế, nếu Bình gửi cho An chiếc hộp có khóa trong đó (và chiếc hộp này không khóa), thì MIT hòan tòan có thể (1) tự đánh cho mình chiếc chìa của khóa này hoặc (2) thay bằng khóa của chính anh ta. Nếu dùng cách (1) thì khi anh ta nhận được chiếc hộp từ An, anh ta dùng chiếc chìa để mở khóa, lấy chiếc nhẫn ra rồi khóa lại như cũ. Nếu dùng cách (2) thì anh ta mở khóa ra, lấy chiếc nhẫn, rồi khóa lại bằng khóa của Bình. Em nghĩ câu hỏi này dùng PKI nhưng áp dụng vào câu hỏi vui vui này thì không ổn lắm.
PKE thi phai rat quan tam den man-in-the-middle, tuy nhien jalfal thay doi voi cau hoi nay, cach nay cua Mg9H la tot nhat roi. Khong biet co con cach nao de cai thien huong cua Mg9H hay khong.
Cách của Mg9H vẫn bị man-in-the-middle attack, bởi vậy tôi mới nói.
Twoask nói đúng. Có thể chữa lại lời giải như sau: An gửi cho Bình cái hộp đựng nhẫn và khóa nó với khóa K1. Bình nhận được hộp, khóa thêm khóa K2 vào và gửi ngược lại cho An. An mở khóa K1 gửi lại cho Bình. Bình dùng chìa của K2 mở hộp.
Cách giải hay quá
Mặc dù vậy cũng ko chống đc kiểu man-in-the-middle kia (ko hiểu sao lại viết tắt là MIT ạ?). Người ở giữa - C - (MIT) nhận đc hộp lần đầu, giữ lại, gửi 1 cái hộp khác khóa bằng khóa của anh ta cho Bình, kệ cho bình xử thế nào thì xử, còn bản thân C khóa hộp bằng khóa K3 của chính hắn, send lại cho A, A mở khóa K1, gửi lại cho Bình, qua tay C, C dùng chìa của anh ta mở khóa K3 và lấy nhẫn.
Theo ý kiến của em nếu giữa A và B ko có 1 sự thỏa thuận trước, thì kiểu gì C cũng có cách lấy đồ thôi
:-), nói túm lại câu đố của tôi chưa ổn. Vấn đề là sự ví von giữa khóa/chìa vật lý và public/private keys trong cryptography chỉ có ý nghĩa trong một phạm vi hẹp. Ví dụ, khó mà dùng khóa/chìa vật lý để làm digital signature, authentication.
Tuy nhiên, chắc chắn là một câu hỏi loại này rất thích hợp cho một interview. Người phỏng vấn có thể đặt ra các scenarios về MiM (không phải MiT) để xem interviewee phản ứng thế nào.
Giải câu 46 nè
Chia tập số thực ra làm n lớp tương ứng với phần thập phân thuộc vào các khoảng [0, 1/n], [1/n,2/n],…, [n-1/n,1].
Nếu trong các số x,2x,..,(n-1)x có 1 số có phần thập phân nằm trong 2 khoảng hoặc [0,1/n] hoặc [n-1/n] thì xong.
Trường hợp còn lại, áp dụng nguyên lý Diricle với n-1 số x,2x,…, (n-1)x cho n-2 khoảng còn lại ta có ít nhất 2 số có phần thập phân nằm trong cùng 1 khoảng.
Hiệu của 2 số này là 1 trong n-1 số x,2x,…,(n-1)x và nằm trong khoảng 1/n của 1 số nguyên