Score:0

สามารถสร้างเลขประจำตัวได้อย่างรวดเร็ว ไม่ชนกัน และไม่มีการเปิดเผยข้อมูลของเลขประจำตัว?

ธง ru

มีวิธีมาตรฐานในการสร้างหมายเลข ID ทีละรายการดังนี้:

  • คุณสามารถรับประกันหรือเกือบจะรับประกันได้ว่าคุณหลีกเลี่ยงการชนกัน (โดยคำว่า "เกือบรับประกัน" ฉันหมายถึง เช่น หากคุณสร้างตัวเลข 24 หลักแบบสุ่มทั้งหมด และคุณ "เท่านั้น" สร้างตัวเลขเหล่านี้ได้ 1 ล้านตัวเลข ดังนั้นแม้จะมีความขัดแย้งในวันเกิด โอกาสที่จะเกิดการชนกันก็จะน้อยมาก)
  • คุณต้องการให้หมายเลข ID สั้น ไม่เทอะทะ โดยเฉพาะคุณ อย่า ต้องการพึ่งพาความยาวของหมายเลข ID (และการเลือกค่าสุ่ม) เพื่อหลีกเลี่ยงการชนกัน ดังที่อธิบายไว้ในหัวข้อย่อยก่อนหน้า คุณต้องทำอย่างอื่น
  • คุณไม่ต้องการหลีกเลี่ยงการชนกันในแต่ละครั้งที่คุณสร้างค่าใหม่โดยดูที่ค่าที่มีอยู่แล้วทั้งหมดเพื่อดูว่าค่านั้นถูกใช้ไปแล้วหรือไม่ นี่จะเป็นการค้นหาบันทึก (n) แต่ละครั้งในรายการที่เรียงลำดับ แต่สมมติว่าฉันต้องการหลีกเลี่ยงสิ่งนี้
  • คุณไม่ต้องการให้หมายเลข ID เปิดเผยข้อมูลใด ๆ เกี่ยวกับเวลาที่สร้างขึ้น หรือจำนวน ID ที่สร้างขึ้นระหว่าง ID X และ Y หากไม่มีเงื่อนไขนี้ ปัญหาก็เล็กน้อย คุณสามารถใช้เวลานาฬิกา (บวกค่าสุ่มที่ใหญ่พอที่จะหลีกเลี่ยงการชนกันระหว่างตัวเลขที่สร้างในค่าเวลานาฬิกาเดียวกัน) หรือคุณสามารถใช้จำนวนเต็มตามลำดับ (ยกเว้นตอนนี้ผู้โจมตีรู้ว่าหากมีคนสร้างค่า ID 5000 บน วันที่ 1 มีนาคม และค่า ID 6000 ในวันที่ 1 เมษายน มีค่าอื่นๆ อีก 1,000 ค่าที่สร้างขึ้นในระหว่างนั้น)

ฉันพยายามหาคำตอบเล็กน้อย แต่คำตอบที่ฉันพยายามดูเหมือนจะไม่ได้ผล คุณสามารถใช้แฮช SHA-256 ของตัวเลข 1, 2, 3 และอื่น ๆ (รวมถึงรหัสลับ) แต่สิ่งนี้มีปัญหาเหมือนกับการเลือกตัวเลขสุ่มจากพื้นที่ว่าง - หากคุณพึ่งพา ความยาวของแฮช (เช่น SHA-256) เพื่อหลีกเลี่ยงการชนกัน หมายเลข ID ที่ได้จะยาวและเทอะทะ และหากคุณทำให้แฮชสั้นลง จะเพิ่มโอกาสในการชนกัน

หรือคุณสามารถสร้างรหัสใหม่โดยเพิ่มค่าสุ่มระหว่าง 1 ถึง n แต่ละครั้ง แทนที่จะเพิ่มครั้งละ 1 เสมอ ปัญหาคือ ขึ้นอยู่กับว่าผู้โจมตีสามารถทำอะไรได้บ้าง พวกเขาอาจรู้ได้ว่า n คืออะไร -- ถ้าพวกเขามี ความสามารถในการสร้างสอง ID ตามลำดับ และทำซ้ำๆ พวกเขาสามารถหา n หรือถ้าพวกเขามีความสามารถในการตรวจสอบว่า ID ใดถูกต้อง พวกเขาสามารถตรวจสอบทุกตัวเลขในช่วงเล็กๆ เพื่อดูว่าการบรรจุ ID ที่ถูกต้องแน่นแค่ไหน ID คือ และหา n จากสิ่งนั้น

วิธีแก้ปัญหาเดียวที่ฉันพบมีดังนี้ ขั้นแรก เตรียมงานล่วงหน้า สำหรับค่า ID จำนวนมากที่คุณคาดว่าจะสร้าง (เช่น 1 ล้าน) ให้นำจำนวนเต็มทั้งหมดตั้งแต่ 1 ถึง 1 ล้าน และตามลำดับ ให้เริ่มคำนวณแฮชของจำนวนเต็มบวกรหัสลับ ตัดแฮชเป็นค่าใดก็ได้ที่คุณคิดว่าสั้นพอ แต่ด้วยการตัดสั้นพอ คุณคาดว่าจะเห็นการชนกัน ดังนั้น ทุกครั้งที่คุณสร้างแฮชแบบตัดใหม่สำหรับจำนวนเต็มที่กำหนด ให้ตรวจสอบกับค่าที่สร้างไว้ก่อนหน้านี้ และหากมีการชนกัน ให้เพิ่มจำนวนเต็มนั้นลงในรายการ L ของจำนวนเต็ม โดยที่แฮชของจำนวนเต็มนั้นชนกับจำนวนเต็มน้อยกว่า (อันที่จริง หากแผนของคุณคือสร้าง 1 ล้าน ID ในระหว่างเตรียมงาน คุณจะต้องเผื่อจำนวนเต็ม 1 ล้านสุดท้ายเล็กน้อย เพื่อชดเชยจำนวนเต็มที่คุณข้ามไป)

จากนั้น ในขณะดำเนินการเมื่อคุณสร้าง ID ของคุณ คุณจะเริ่มต้นด้วยตัวนับจำนวนเต็ม แต่ละครั้งที่คุณสร้าง ID ใหม่ คุณจะเพิ่มจำนวนเต็มและตรวจสอบว่ามันอยู่ในรายการ L ของคุณหรือไม่ และถ้าใช่ คุณจะข้ามและไปที่จำนวนเต็มถัดไป (สิ่งนี้เกี่ยวข้องกับ "การค้นหา log n" ซึ่งดูเหมือนจะเป็นการละเมิดกฎข้อหนึ่งที่ฉันระบุไว้ แต่สิ่งที่ฉันต้องการทำจริงๆ คือหลีกเลี่ยงการตรวจสอบค่า ID ใหม่แต่ละค่าเทียบกับทุกค่าที่สร้างขึ้นจนถึงตอนนี้ การตรวจสอบ L ควรเร็วกว่ามาก) และคุณสามารถปรับแต่งสิ่งนี้สำหรับการแลกเปลี่ยน (ยิ่งคุณสร้างแฮชที่ถูกตัดให้สั้นลง L ก็จะยิ่งสั้นลง และด้วยเหตุนี้ การตรวจสอบแต่ละครั้งก็จะสั้นลงทุกครั้งที่คุณสร้าง ID ใหม่ แต่ค่า ID ที่ยาวขึ้นอาจไม่เป็นที่พึงปรารถนา)

แต่นี่รู้สึกเหมือนเป็นแฮ็ก มีวิธีมาตรฐานหรือไม่? ถ้าไม่ คุณคิดวิธีที่ดีกว่านี้ได้ไหม

kelalaka avatar
in flag
สำหรับคีย์คงที่ ให้เข้ารหัสด้วยโหมด AES-ECB AES เป็นตระกูลของการเรียงสับเปลี่ยนและคีย์ให้เลือกหนึ่งในนั้น นอกจากนี้ ฉันจะเลือก SHA-512, SHAKE หรือ BLAKE-512 เป็นต้น ไม่คาดว่าจะพบการชนกัน อย่างไรก็ตาม เมื่อคุณพบ คุณจะมีชื่อเสียงมาก!
poncho avatar
my flag
@kelalaka: SHA-512? คุณกำลังแนะนำรหัส 512 บิต (154 หลัก) ???
kelalaka avatar
in flag
คุณคิดว่าคุณสามารถมี ID มากกว่า $2^{100}$ ได้ไหม
poncho avatar
my flag
@kelalaka: หากคุณใช้การต้านทานการชนกันของ SHA-512 คุณต้องส่งออกแฮชแบบเต็ม - แฮชที่ถูกตัดจะไม่บ่งบอกถึงการชนกันในฟังก์ชันแฮชดั้งเดิม
Bennett avatar
ru flag
ปัญหาเกี่ยวกับการใช้แฮชประเภทใดๆ เพื่อสร้าง ID นั้นเป็นปัญหาเดียวกันกับการใช้ตัวเลขสุ่ม ดังที่อธิบายไว้ในคำชี้แจงปัญหา -- หากคุณหลีกเลี่ยงการชนกันโดยเพียงแค่ทำให้มันยาว นั่นจะเป็นการเทอะทะเกินไป และถ้าคุณตัดมันให้สั้นลง ทำให้สั้นลง เพิ่มโอกาสในการชนกัน ฉันกำลังมองหาวิธีหลีกเลี่ยงการชนกันโดยไม่เพียงแค่ใช้ค่าที่ยาวมากๆ
Score:2
ธง my

วิธีที่มีประสิทธิภาพที่สุดคือการใช้ อัลกอริทึมการเข้ารหัสการรักษารูปแบบ; นั่นคืออัลกอริทึมที่เป็นการเปลี่ยนแปลงในชุดขนาดตามอำเภอใจ (เช่น ลำดับทศนิยม 10 หลัก)

การใช้มันจะง่าย: คุณจะเลือกคีย์สุ่มและเก็บไว้ คุณต้องเก็บหมายเลขลำดับไว้ด้วย (ในรูปแบบเดียวกับเอาต์พุต เช่น คุณอาจขึ้นต้นด้วย 0000000000) จากนั้น เมื่อถึงเวลาสร้าง ID ถัดไป คุณต้องเพิ่มหมายเลขลำดับ และส่งผ่านอัลกอริทึม FPE นั่นคือ ID ต่อไปของคุณ [1]

เนื่องจากอัลกอริทึม FPE เป็นการเรียงสับเปลี่ยน คุณจะไม่สร้าง ID เดียวกันซ้ำสองครั้งจนกว่าจะมีการตัดหมายเลขลำดับ จึงไม่มีการชนกัน คุณสามารถสร้างรหัสให้สั้นได้ตามต้องการ (อัลกอริทึม FPE ในปัจจุบันมีปัญหาเกี่ยวกับพื้นที่ขนาดเล็กมาก หากคุณรักษารหัสให้มีความยาวอย่างน้อย 6 หลัก คุณจะปลอดภัย) และเนื่องจากอัลกอริทึม FPE มีความปลอดภัย ID ใดๆ จึงไม่ให้ข้อมูลใดๆ เกี่ยวกับ ID อื่นๆ (รวมถึงลำดับการสร้างที่สัมพันธ์กัน)

ข้อเสีย: ไม่มีไลบรารี FPE ทั่วไป (เท่าที่ฉันรู้) สำหรับการใช้งานฉันอยากจะแนะนำ FF1 จากเอกสารนี้; การนำไปใช้ตั้งแต่เริ่มต้นจะเป็นงานเล็กน้อย (แต่จะตอบสนองความต้องการของคุณ)


วิธีที่มีประสิทธิภาพน้อยกว่าแต่นำไปใช้ได้ง่ายกว่าคือทำการเปลี่ยนแปลงในสิ่งที่คุณแนะนำ: เก็บรายการ ID ที่คุณยังไม่ได้กำหนด

ที่นี่ ระหว่างการตั้งค่า คุณจะต้องเริ่มต้นรายการ ID ที่เป็นไปได้ทั้งหมดตามลำดับ เช่น 000000 ถึง 999999 นอกจากนี้ คุณจะต้องตั้งค่า N เป็น ID สูงสุดที่ไม่ได้กำหนด (ในตัวอย่างนี้ N = 999999)

จากนั้น เมื่อถึงเวลาออก ID ใหม่ คุณจะเลือกตัวเลขสุ่ม x ระหว่าง 0 ถึง N (รวม) จากนั้น คุณจะสลับรหัสที่ดัชนี N และ x (และถ้า x=N การดำเนินการสลับนี้จะไม่ทำอะไรเลย) จากนั้น คุณจะส่งออกค่าที่ไม่อยู่ในดัชนี N (แล้วลดลง N)

แค่นั้นแหละ; นี้เป็นจริง ฟิชเชอร์-เยตส์สับเปลี่ยนคุณสามารถทำสิ่งนี้ได้ตามต้องการ (ตามที่ฉันเขียนไว้) หรือคุณสามารถทำการสับทั้งหมดในเวลาตั้งค่า (และเพียงแค่อ่านสิ่งต่าง ๆ นอกรายการเมื่อสร้าง ID)

การดำเนินการนี้มีประสิทธิภาพน้อยกว่าแนวคิด FPE เนื่องจากการตั้งค่ามีความเกี่ยวข้องมากกว่า และคุณต้องเก็บรายการ ID จำนวนมากไว้รอบๆ ในทางกลับกัน มันง่ายกว่าการพยายามใช้ FF1 ตั้งแต่เริ่มต้น...


[1]: อัลกอริทึมการเข้ารหัสที่รักษารูปแบบยังคงใช้ 'ปรับแต่ง'; คุณต้องการคงค่านั้นไว้ (เช่น สตริงว่าง) การปรับแต่งให้บริการที่คุณไม่จำเป็นต้องใช้โดยเฉพาะ

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา