แนวคิดของการดำเนินการเบื้องต้นเมื่อความซับซ้อนอยู่ในรูปของ $2^{128}$

สำหรับอัลกอริทึมอื่นๆ สัญกรณ์ big-O มักจะซ่อนตัวประกอบคงที่ ทำให้การดำเนินการเบื้องต้นที่แน่นอนเป็นรายละเอียดที่ไม่สำคัญ แต่เอกสารการเข้ารหัสระบุความซับซ้อนอย่างชัดเจน ซึ่งทำให้ฉันประหลาดใจ

คุณจะต้องประหลาดใจแน่นอน --- โดยทั่วไป การเขียน "ความซับซ้อนที่แน่นอน" นั้นไร้ความหวังเนื่องจากสิ่งที่เรียกว่า ทฤษฎีบทเร่งความเร็วเชิงเส้น --- เราสามารถตรึงความซับซ้อนของการคำนวณไว้ที่ปัจจัยการคูณตามอำเภอใจเท่านั้น เนื่องจากเราสามารถเพิ่มขนาดของตัวอักษรพื้นฐานได้เสมอด้วยปัจจัยคงที่เพื่อให้เราสามารถคำนวณจำนวนการดำเนินการต่อหน่วยเวลาได้มากขึ้น สิ่งนี้ (ประเภท) มีองค์ประกอบที่ใช้งานได้จริง --- คุณสามารถเพิ่มขนาดของสถาปัตยกรรมชุดคำสั่งเพื่อทำการคำนวณเพิ่มเติมต่อรอบสัญญาณนาฬิกา (ที่ต้นทุนของชิปที่ใช้ซิลิคอนมากขึ้น)

ผู้คนใช้เมตริกต้นทุนอะไร มัน จริงๆ ขึ้นอยู่กับการสมัคร ตัวอย่างเช่น การโจมตี AES ที่รู้จักกันดีคือ การโจมตีแบบ Bicliqueซึ่งกู้คืนคีย์ AES ในความซับซ้อน $2^{126.1}$. แน่นอน ผู้เขียนมักจะไม่อ้างตัวเลขตามอำเภอใจว่าเป็นผลลัพธ์ --- พวกเขาจะคำนวณสิ่งนี้ได้อย่างไร

ความซับซ้อนเต็มรูปแบบของแนวทาง biclique ที่เป็นอิสระ มีการประเมินดังนี้ $$C_{full} = 2^{nâ2d}[C_{biclique} + C_{precomp} + C_{recomp} + C_{falsepos}],$$ ที่ไหน

• $C_{พรีคอม}$ คือความซับซ้อนของการคำนวณล่วงหน้าในขั้นตอนที่ 3 ซึ่งมีค่าเท่ากับน้อยกว่า $2^d$ การรันของ subcipher $g$.
• $C_{recomp}$ คือความซับซ้อนของการคำนวณใหม่ของตัวแปรภายใน $v$ $2^{2d}$ ครั้ง. มัน ขึ้นอยู่กับคุณสมบัติการแพร่กระจายของรหัสเป็นอย่างมาก สำหรับ AES ค่านี้จะแตกต่างกันไปตั้งแต่ $2^{2dâ1.5}$ ถึง $2^{2dâ4}$. โครงสร้างแบบ biclique ค่อนข้างถูกในกระบวนทัศน์นี้ วิธีการในส่วนที่ 3.1 เปิดใช้งาน สร้างบิกลิคในเท่านั้น $2^{d+1}$ การโทรของ subcipher $f$. ดังนั้นโดยปกติจะเป็นคีย์เต็ม ความซับซ้อนในการกู้คืนจะถูกครอบงำโดย $2^{nâ2d}C_{recomp}$. ทั้งนี้ขึ้นอยู่กับ ความกว้างของตัวแปรที่ตรงกันและขนาด biclique $d$ ด้วย. เราให้รายละเอียดเพิ่มเติมสำหรับกรณี ของ AES ในหัวข้อต่อไป ความซับซ้อนของหน่วยความจำของการกู้คืนคีย์มีขอบเขตบน โดยจัดเก็บ $2^d$ การคำนวณเต็มรูปแบบของรหัส

โดยเฉพาะอย่างยิ่งสำหรับ AES พวกเขากล่าวว่า

รวมกันแล้วเราต้องการเท่ากับ $3.4375$ การดำเนินการ SubBytes (เช่น 55 S-boxes), 2.3125 การดำเนินการ MixColumns และ XOR จำนวนเล็กน้อยในกำหนดการสำคัญ จำนวน การคำนวณ SubBytes เห็นได้ชัดว่าเป็น summand ที่ใหญ่กว่า S-boxes ยังเป็นผู้สนับสนุนรายใหญ่อีกด้วย ไปจนถึงความซับซ้อนในทางปฏิบัติของ AES ทั้งในด้านฮาร์ดแวร์และซอฟต์แวร์ ดังนั้น หากเราตั้งเป้าว่า ตัวเลขเดียวที่อ้างถึงความซับซ้อน การนับจำนวน SubBytes เป็นเรื่องที่สมเหตุสมผล การดำเนินการที่เราต้องการและเปรียบเทียบกับรหัสเต็ม เลขหลังคือ $10 + 2.5 = 12.5$ เนื่องจากเราต้องคำนึงถึงความไม่เชิงเส้นของตารางเวลาที่สำคัญ ผลที่ตามมา, $C_{recomp}$ เทียบเท่ากับ $2^{16}\คูณ 3.4375/12.5 = 2^{14.14}$ การทำงานของ AES-128 เต็มรูปแบบ ค่า $C_{บิกลิค}$ และ $C_{พรีคอม}$ รวมกันไม่เกิน $2^8$ การโทรของ AES-128 แบบเต็ม ความซับซ้อนในการคำนวณทั้งหมดอยู่ที่ประมาณ $2^{112} (2^7 + 2^7 + 2^{14.14} + 2^8) = 2^{126.18}$.

นี่คือการบอกว่า "การดำเนินการดั้งเดิม" ของการโจมตีแบบ biclique คือจำนวนการเรียกใช้ SubBytes ซึ่งจะทำให้สิ่งต่าง ๆ เป็นปกติเพื่อให้การโจมตีด้วยกำลังดุร้าย $2^{128}$ ความซับซ้อน

แน่นอนว่ามีแนวคิดที่ซับซ้อนอื่น ๆ ตัวอย่างเช่น

• ฉันเคยได้ยินเกี่ยวกับเมตริก "พื้นที่ x เวลา" ซึ่งวัดความซับซ้อนของการโจมตีในแง่ของเวลาที่ต้องใช้วงจรขนาดหนึ่งเพื่อทำให้เสร็จสมบูรณ์ (แต่ไม่สามารถหาข้อมูลอ้างอิงได้ในขณะนี้)

• ในทำนองเดียวกัน เป็นเรื่องปกติที่การโจมตีจะวัดทั้งแนวคิดบางอย่างเกี่ยวกับความซับซ้อนของการคำนวณพร้อมกับแนวคิดบางอย่างเกี่ยวกับความซับซ้อนของหน่วยความจำ/ตัวอย่าง

• ในการเข้ารหัสแบบ lattice เมตริกบางอย่างที่เรียกว่า "Core SVP count" ค่อนข้างเป็นที่นิยมในการวิเคราะห์

โดยทั่วไปแม้ว่าจะไม่ชัดเจนว่าอะไร $2^{128}$ การดำเนินการดั้งเดิมหมายถึง (ตัวอย่าง) มันขึ้นอยู่กับผู้เขียนที่จะกำหนดเงื่อนไขเหล่านี้ ดังนั้นโดยทั่วไปแล้ว