ฉันสงสัยเกี่ยวกับย่อหน้านี้มาระยะหนึ่งแล้ว:
การคูณเป็นฟังก์ชันการผสมที่ยอดเยี่ยม หากคุณคิดว่าการคูณมีลักษณะอย่างไรในแง่ของ AND และ XOR จะเห็นได้ชัดว่าการคูณแบบ 64 บิตซับซ้อนเพียงใด จำนวนทรานซิสเตอร์ที่ต้องใช้ในฮาร์ดแวร์ห้ามไม่ให้มีการใช้การคูณในอัลกอริธึมการเข้ารหัสส่วนใหญ่ แต่สำหรับ PRNG ที่ไม่ใช่การเข้ารหัสซึ่งจำเป็นต้องทำงานบน CPU วัตถุประสงค์ทั่วไปเท่านั้น การคูณจะมีประโยชน์มากเนื่องจากมีการใช้งานฮาร์ดแวร์อยู่แล้ว
https://tom-kaitchuck.medium.com/designing-a-new-prng-1c4ffd27124d
โดยปกติแล้วในอัลกอริทึมการเข้ารหัส เราใช้การเพิ่มเติมโมดูลาร์ การหมุน และการดำเนินการ OR แบบเอกสิทธิ์เฉพาะบุคคล แต่มีอะไรที่อาจขัดขวางการใช้การคูณแบบโมดูลาร์ การหมุน และการดำเนินการ OR แบบเอกสิทธิ์เฉพาะบุคคลหรือไม่
การคูณแบบแยกส่วนจะช้ากว่าการบวก แต่อาจไม่ได้ช้ากว่ากันมากนัก และแน่นอนว่าเป็นฟังก์ชันการผสมที่แรงกว่า การคูณเป็นฟังก์ชันการผสมที่ยอดเยี่ยม แต่ทำไมจึงไม่ค่อยใช้ในการเข้ารหัสแบบสมมาตร ฉันคิดว่าแม้แต่สมาร์ทโฟนก็สามารถทำการคูณแบบ 64 บิตได้อย่างรวดเร็วและมีการใช้ฮาร์ดแวร์สำหรับการคูณ (แต่ฉันไม่แน่ใจ)
ความช้าของการคูณเป็นปัญหาใหญ่ที่การคูณไม่พบการใช้งานอย่างแพร่หลายในอัลกอริทึมการเข้ารหัสที่รวดเร็วและน้ำหนักเบาใช่หรือไม่ อาจเป็นปัญหาบนอุปกรณ์ IOT หรือชิป RFID แต่เมื่อพูดถึงคอมพิวเตอร์และสมาร์ทโฟน อัลกอริทึมการเข้ารหัสที่อิงตามการคูณจะไม่เป็นปัญหาใช่ไหม
ความช้าของการคูณเป็นปัญหาใหญ่ที่การคูณไม่พบการใช้งานอย่างแพร่หลายในอัลกอริทึมการเข้ารหัสที่รวดเร็วและน้ำหนักเบาใช่หรือไม่ อาจเป็นปัญหาบนอุปกรณ์ IOT หรือชิป RFID แต่เมื่อพูดถึงคอมพิวเตอร์และสมาร์ทโฟน อัลกอริทึมการเข้ารหัสที่อิงตามการคูณจะไม่เป็นปัญหาใช่ไหม
ส่วนหนึ่งของปัญหาดูเหมือนจะเป็นคำจำกัดความของคำว่า 'lightweight' และแพลตฟอร์มที่ตั้งใจให้เป็นเป้าหมาย ซีพียูบนสมาร์ทโฟนมีความสามารถจริง ฉันจะไม่อธิบายลักษณะแพลตฟอร์มเหล่านั้น (หรือคอมพิวเตอร์แล็ปท็อป) ว่าจำเป็นต้อง 'เบา' โดยทั่วไป crypto ที่มีน้ำหนักเบาได้รับการออกแบบโดยคำนึงถึงไมโครคอนโทรลเลอร์ โดยทั่วไปแล้วไมโครคอนโทรลเลอร์เหล่านั้นไม่มีคำสั่งการคูณแบบ 64x64 บิตในตัว
ตอนนี้ การคูณแบบโมดูลาร์ (สำหรับโมดูลัสยกกำลัง 2) สามารถดำเนินการได้โดยชุดของการเปลี่ยนแปลงและการเพิ่มเงื่อนไข ทำได้แน่นอน แต่มีราคาแพงกว่าการดำเนินการเพิ่มเติม
ปัญหาอื่น ๆ ดูเหมือนจะเป็นการคูณแบบแยกส่วนไม่ได้ยอดเยี่ยมอย่างที่คุณคาดหวัง สำหรับการสนทนานี้ ฉันจะจำกัดการสนทนาของฉันไว้ที่การคูณโมดูโล a ยกกำลัง 2 (หลายโมดูโล a ไพรม์ไม่มีปัญหาเหล่านี้ พวกเขามีปัญหาเกี่ยวกับช่วงที่ไม่เป็นยกกำลัง 2)
การคูณแบบแยกส่วนไม่มีการเผยแพร่ 'คำที่ถูกต้อง' ตัวอย่างเช่น การพลิกบิตสูงของหนึ่งในอินพุตจะส่งผลต่อบิตสูงของเอาต์พุตเท่านั้น บิตอื่น ๆ จะไม่ได้รับผลกระทบ แน่นอนว่าการเพิ่มโมดูลาร์ก็มีปัญหาเช่นเดียวกัน แต่ก็ยังถูกกว่า
การคูณแบบแยกส่วนมีความแตกต่างอย่างมาก ความแข็งแกร่งขึ้นอยู่กับตัวตน $(-x)*y = -(x*y)$ (และการทำงานของโมดูลัสไม่ได้ทำให้สิ่งนี้แตกสลาย)
ประเด็นทั้งสองนี้สามารถออกแบบได้อย่างเหมาะสม อย่างไรก็ตาม ข้อเท็จจริงที่คุณต้องทำเช่นนั้นทำให้ความน่าสนใจลดลง นอกจากนี้ยังทำให้เกิดคำถาม: ทำไมไม่ใช้การคูณ $GF(2^k)$ แทน? หากเรากำลังดำเนินการแบบ shift/add การปรับใช้การคูณแบบ Galois แบบ double/xor นั้นไม่ได้มีราคาแพงกว่ามากนัก และเป็นการหลีกเลี่ยงสองประเด็นข้างต้น...
รหัสบล็อก ความคิด จากปี 1991 ใช้ modular multiplication mod $2^{16}+1$ สำหรับการแพร่ (โดยที่ 0 ถูกแมปกับ $2^{16}$).
เนื่องจากตัวหารศูนย์ไม่ดีจากมุมมองของการเข้ารหัส โมดูลัสควรเป็นจำนวนเฉพาะและอยู่ในรูปแบบ $2^b+1$ เนื่องจากคนชอบทำงานกับบิต (และไม่ใช้ 0) ดังนั้น $b=2, 4, 8, 16$ ($b=1$ จะเป็นเส้นตรง)
หากคุณออกแบบรหัสโดยใช้การคูณแบบแยกส่วน คุณจะพบกับปัญหา (อย่างน้อย) 2 ประการ:
การเข้ารหัสทุกประเภทมีค่าใช้จ่ายสูงในด้านฮาร์ดแวร์และพลังงาน ตัวคูณมีขนาดใหญ่และลึกและช้าเมื่อเทียบกับตัวบวกเต็ม ALU พื้นฐาน ฉันจะโบกมือเป็นจังหวะ แต่ถ้าคุณคว้าหนังสือสถาปัตยกรรม CPU คุณจะพบสิ่งต่อไปนี้: การออกแบบตัวคูณนั้นแตกต่างกันเสมอ แต่ไปป์ไลน์หน่วย MUL สำหรับผลลัพธ์ 64 บิตคือ 4 -deep และสำหรับผลลัพธ์ 128 บิตคือ 8-deep สำหรับ CPU ส่วนใหญ่ นี่เป็นเพราะคุณใช้บล็อกตัวบวกแบบเต็มแบบโยงใย และความลึกสูงสุดในการออกแบบ 4 ความลึกคือ 16 ความลึกของตัวบวกแบบเต็มสำหรับ XOR, ROL หรือ ADD เทียบเท่ากับตัวบวกแบบเต็มตัวเดียว โปรเซสเซอร์ Super-scaler ซ่อนความล่าช้าของตัวคูณไว้มาก อย่างไรก็ตาม หากคุณกำลังยุ่งอยู่กับปัญหาจริงๆ จะพบไปป์ไลน์ที่ว่างเปล่าพร้อมความล่าช้าอย่างมาก
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
