สำหรับอัลกอริทึมอื่นๆ สัญกรณ์ 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}$ การดำเนินการดั้งเดิมหมายถึง (ตัวอย่าง) มันขึ้นอยู่กับผู้เขียนที่จะกำหนดเงื่อนไขเหล่านี้ ดังนั้นโดยทั่วไปแล้ว