ยินดีต้อนรับสู่ฟอรัม @vnd !
คำถามของคุณอาจแก้ไขได้โดยใช้ ตามแฮช เค- ไม่เปิดเผยชื่อ? ตามที่ฉันเข้าใจ วิธีการนี้จะ:
- ป้องกันไม่ให้มัลลอรี่ค้นพบวันเกิดของอลิซ
- ป้องกันไม่ให้อลิซรู้วันเกิดของเพื่อนร่วมชั้น; และ
- อนุญาตให้อลิซค้นพบว่ามีเพื่อนร่วมชั้นคนใดของเธอที่มีวันเกิดร่วมกับเธอเท่านั้น
สมมติว่าอลิซมีเพื่อนร่วมชั้น 12 คนซึ่งมีตารางนี้แสดงข้อมูล:
()
บ๊อบ 11 ม.ค. 2544 a40b69b979ef6af5e9f13a49cfc568d8b942d5c2 a40b6
โจ 23 มี.ค. 2532 4fde4b6b8e077d5b51eed716ab3d94a6ac04c45e 4fde4
เบ็น 9 มิถุนายน 2545 46885da4ffaa4c3d1b31413f96c38f2cb7e895ea 46885
ศิลปะ 4 ธันวาคม 2548 a40b6425e2a7a93a9ac95ee275a5398397c46dd2 a40b6
ทอม 17 พ.ย. 2520 a49e374c34333b86ccf08bc10d6e04312e772c41 a49e3
ทิม 3 ก.ค. 2532 39e95ac6c6286e6f036822f3fa31131a2e892b08 39e95
เอมี่ 12 ก.พ. 2545 92dac31b3d3a0793fd2845081c93024d0ea8ac8c 92dac
อีวา 24 เมษายน 2533 a0ed580e3df29f9a8f22276092ac9f58117401ec a0ed5
ฟ้อง 10 ก.ค. 2546 a93703839d02a539c12841f5de2ec8790107925b a9370
Zoe 5 ม.ค. 2549 a40b6232f910b358e971e4c5f91e273c07499ab0 a40b6
เลีย 18 ธ.ค. 2521 addc1fc5fbe7dea93e3bd1d421521f005ba89c8e addc1
เคย์ 4 ส.ค. 2533 a4e15e622b89d302f2b0357c2b2efc0d38fba7a0 a4e15
อลิซ 11 ม.ค. 2544 a40b69b979ef6af5e9f13a49cfc568d8b942d5c2 a40b6
ข้อมูลตาราง
ตารางนี้มีชื่อที่กำหนด วันเดือนปีเกิด (ในรูปแบบทหาร ด้วยเหตุผลด้านความงาม); ค่าแฮชของวันเกิดโดยใช้แฮช (MUH) ที่ไม่มีอยู่จริงและกราฟ 5 กราฟแรกของแฮช (แฟรกเมนต์)
ขั้นตอน
. อลิซคำนวณข้อความย่อยของวันเกิดของเธอโดยใช้แฮชที่สร้างขึ้น (สามารถใช้แฮชใดก็ได้ แม้แต่ SHA1 ที่อ่อนแอ)
. แทนที่จะสื่อสารค่าแฮชทั้งหมดให้กับมัลลอรีซึ่งจะถูกมองว่าเป็นภัยคุกคาม อลิซให้แฮชเพียงส่วนย่อยๆ ของเธอแก่มัลลอรี: ห้ากราฟแรก (ปรับได้)
. มัลลอรี่รู้วันเกิดของทุกคนในชั้นเรียน ยกเว้นอลิซ Mallory คำนวณแฮชของวันเกิดของเพื่อนร่วมชั้นแต่ละคน และส่งคืนข้อมูลนั้นให้กับอลิซ แต่เฉพาะเมื่อส่วนของอลิซตรงกับแฟรกเมนต์เดียวกันของแฮชแบบเต็มเท่านั้นข้อมูลที่ส่งกลับไม่รวมแฟรกเมนต์ เนื่องจากจะเป็นการซ้ำซ้อน
อย่ า ย า ย . ใช้แฟรกเมนต์ 5 กราฟ a40b6
มัลลอรี่จะให้ข้อมูลต่อไปนี้กับอลิซ
9b979ef6af5e9f13a49cfc568d8b942d5c2
425e2a7a93a9ac95ee275a5398397c46dd2
232f910b358e971e4c5f91e273c07499ab0
   และอลิซจะดูว่าส่วนของเธอและการตอบสนองตรงกับแฮชทั้งหมดของเธอหรือไม่ ในกรณีนี้ ข้อแรกคือการจับคู่และอลิซมีคำตอบ ตอนนี้เธอรู้แล้วว่ามีใครบางคนในชั้นเรียนมีวันเกิดร่วมกับเธอ แม้ว่าเธอจะไม่รู้จักตัวตนของพวกเขาก็ตาม
ในการแลกเปลี่ยนนี้ เราเห็นว่า Mallory ได้รับเพียงเศษเสี้ยว จึงไม่สามารถระบุได้ว่าแฮชที่เธอคำนวณนั้นตรงกับแฮชที่แท้จริงของอลิซหรือไม่ เนื่องจากเธอไม่มีทางคำนวณแฮชทั้งหมดของอลิซได้
ความเป็นไปได้ของภัยคุกคามถูกกำจัดเนื่องจากการตัดสินใจว่ามีการแข่งขันหรือไม่นั้นไม่สามารถระบุได้โดย Mallory (เซิร์ฟเวอร์ที่ไม่เป็นมิตร) แต่จะถูกกำหนดโดย Alice (ลูกค้าที่ซื่อสัตย์เท่านั้น)
นอกจากนี้ การใช้ข้อมูลที่มัลลอรี่ให้มา อลิซไม่สามารถอนุมานวันเกิดของเพื่อนร่วมชั้นคนใดคนหนึ่งได้ ยกเว้นวันเกิดที่ตรงกับแฮชของเธอ การแข่งขันบางส่วนไม่สามารถหาข้อสรุปได้
จำนวนข้อมูลที่ส่งคืนสามารถปรับได้ตามขนาดของแฟรกเมนต์:
อย่ า ย า ย . การใช้แฟรกเมนต์อักขระตัวเดียว ก
มัลลอรี่จะให้ข้อมูลต่อไปนี้แก่อลิซ:
40b69b979ef6af5e9f13a49cfc568d8b942d5c2
40b6425e2a7a93a9ac95ee275a5398397c46dd2
f9e374c34333b86ccf08bc10d6e04312e772c41
0ed580e3df29f9a8f22276092ac9f58117401ec
93703839d02a539c12841f5de2ec8790107925b
40b6232f910b358e971e4c5f91e273c07499ab0
4e15e622b89d302f2b0357c2b2efc0d38fba7a0
หมายเหตุ: วิธีการนี้ไม่ต้องการให้เรารู้ว่ามีวันเกิดกี่วันเกิด (365) จะสามร้อยสี่ล้านก็ไม่สำคัญ