ภาพใหญ่: รหัสนี้จำเป็นต้องคำนวณโพลิโนเมียลโมดูโลไบนารีผกผัน $พี$ ของพหุนามเลขฐานสองที่ไม่ใช่ศูนย์ทุกตัว $R$ ระดับต่ำกว่าของ $พี$. ในการนี้ ได้เลือกการสร้างพหุนาม $G=1+x$และตาราง $Q_i=G^i\bmod P$ซึ่งเข้าถึงทุกสิ่งที่ต้องการ $R$. ผกผันการคูณของ $R=Q_i$ เป็น $Q_{255-i}$.
รหัสนี้ประเมิน AES S-box และมีค่าผกผันดังนี้:
(บล็อกรหัสเริ่มต้นใน พยายาม
) มันประเมิน p = 0x11b = 283
ที่แสดงถึงพหุนามไบนารี $P=1+x+x^3+x^4+x^8$ เป็นจำนวนเต็ม: ค่าที่ได้รับเมื่อประเมินพหุนามนี้สำหรับจำนวนเต็ม $x=2$. แบบแผนทั่วไปนี้ใช้ใน AES เพื่อจับคู่พหุนามไบนารีกับจำนวนเต็ม
(บล็อกรหัสเริ่มต้นใน ให้ที
) มันคำนวณตาราง Ti]
เป็นตัวแทนของพหุนามไบนารี $Q_i=(1+x)^i\bmod P$ ตามอนุสัญญานี้. ที่ $Q_i$ คำนวณต่อการเกิดซ้ำ $Q_{i+1}=Q_i\,(1+x)\bmod P$ กับ $Q_0=1$แปลเป็น¹ t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))
กับ เสื้อ[0] = 1
ภายใต้อนุสัญญาดังกล่าว
ตัวอย่างเช่น: $Q_0$ คือพหุนาม (ฐานสอง) $1$, แสดงโดย เสื้อ[0] = 1
. $Q_1=1+x$, แสดงโดย เสื้อ[1] = 3
. $Q_2=(1+x)^2=1+x^2$, แสดงโดย เสื้อ[2] = 5
. $Q_7=(1+x)^7=1+x+x^2+x^3+x^4+x^5+x^6+x^7$, แสดงโดย เสื้อ[2] = 0xff = 255
. $Q_8=(1+x)^8\bmod P=(1+x^8)\bmod P=x+x^3+x^4$, แสดงโดย เสื้อ[8] = 0x1a = 26
.
(บล็อกรหัสเริ่มต้นใน ให้ Sbox
) การทำตาราง $Q_i=(1+x)^i\bmod P$ มีประโยชน์เพราะ $(1+x)^{255}\bmod P=1$, ดังนั้น $Q_{255-i}$ คือผลคูณผกผันของ $Q_i$. และ $Q_i$ ถึงพหุนามระดับไบนารีที่ไม่ใช่ศูนย์ทั้งหมด $<8$ (นั่นคือ $1+x$ เป็นเครื่องกำเนิดไฟฟ้า) ดังนั้น จำนวนเต็ม เสื้อ[255 - ฉัน]
แทนค่าผกผันการคูณของพหุนามที่เป็นจำนวนเต็ม Ti]
แสดงถึง และเมื่ออยู่ในวง ผม
ไปจาก 0
ถึง 254
ที่ให้ผลคูณผกผันของแต่ละพหุนามดีกรี 255 ที่ไม่ใช่ศูนย์ $<8$. จากนั้นลูปจะใช้เพียง² การแปลงเลียนแบบที่ระบุในส่วนที่เหลือของ คำจำกัดความของ AES S-box. พหุนามศูนย์เป็นกรณีพิเศษ
ตัวอย่างเช่น: เมื่ออยู่ในลูป ผม = 8
, Ti]
เป็น เสื้อ[8] = 0x1a = 26
เป็นตัวแทน $Q_8=x+x^3+x^4$, และ เสื้อ[255-i]
(กำลังจะ x
, ไม่เกี่ยวข้องกับ $x$) เป็น เสื้อ[247] = 0xfd = 253
เป็นตัวแทนของพหุนาม $Q_{247}=1+x^2+x^3+x^4+x^5+x^6+x^7$. ที่ $Q_{247}$ คือผลคูณผกผันของ $Q_8$. ตามคำจำกัดความของ AES S-box มีเพียงการใช้การแปลงเลียนแบบ²กับ x
แล้วตั้งค่าผลลัพธ์เป็น สบอกซ์[t[i]] = สบอกซ์[26]
.
(ฟังก์ชันผกผัน
) ตารางผกผันคำนวณโดยการค้นหาแต่ละรายการในตาราง ใช้งานได้แต่ไม่มีประสิทธิภาพ InvSbox[i] = sbox.indexOf(i);
อาจถูกแทนที่ด้วยความตรงไปตรงมาและมีประสิทธิภาพมากกว่า InvSbox[sbox[i]] = ผม;
.
¹ เหตุผล: ใน t[i+1] = t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * p))
Ti]
เป็นจำนวนเต็มใน $[0,2^8)$ และเป็นตัวแทน $Q_i$ ของปริญญา $<8$
เ[i] << 1
เป็นจำนวนเต็มคู่ใน $[0,2^9)$ และเป็นตัวแทน $Q_i\,x$.
เ[i] >>> 7
เป็นอย่างใดอย่างหนึ่ง 0
หรือ 1
. มันคือค่าสัมประสิทธิ์ของระยะการสั่งซื้อ $x^7$ ใน $Q_i$.
(t[i] >>> 7) * หน้า
เป็นอย่างใดอย่างหนึ่ง 0
หรือ 0x11b = 283
เป็นตัวแทน $0$ หรือ $พี$.
(t[i] << 1) ^ ((t[i] >>> 7) * p)
เป็นตัวแทนที่สอดคล้องกัน $(Q_i\,x)$ หรือ $(Q_i\,x)+P$, และ (โดยการตรวจสอบทั้งสองกรณี) เป็นจำนวนเต็มใน $[0,2^8)$จึงแสดงถึงพหุนามไบนารีของดีกรี $<8$ซึ่งก็เป็นเช่นนั้น $(Q_i\,x)\bmod P$.
t[i] ^ ((t[i] << 1) ^ ((t[i] >>> 7) * พี))
จึงเป็นจำนวนเต็มใน $[0,2^8)$ และเป็นตัวแทน $Q_i+(Q_i\,x)\bmod P)=Q_i\,(1+x)\bmod P=Q_{i+1}$,ของปริญญา $<8$.
ใน C สำนวนมาตรฐานของเวลาคงที่น่าจะเป็น (โดยหลักแล้วคือ with & -
ใช้แทนการคูณ):
t[i+1] = t[i] ^ ((t[i] << 1) ^ (p & -(t[i] >> 7)))
.
หมายเหตุ: คอมไพเลอร์ C ที่กระตือรือร้นบางตัวจะเห่าผิดที่ -
ปิดปากพวกเขา
² คำสั่ง x |= x << 8;
ทำซ้ำบิตในตัวแปร x
(แทนโมดูลาร์ผกผันของ $Q_i$) เพื่อให้การเลื่อนไปทางขวาที่ตามมาเทียบเท่ากับการหมุนเมื่อพูดถึง 8 บิตลำดับต่ำ คำสั่ง x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
ดำเนินการ เมทริกซ์หมุนเวียน การคูณ แล้ว ^ 0x63
(แทนพหุนาม $1+x+x^5+x^6$) เป็นการบวกค่าคงที่ และ & 0xFF
รักษาลำดับต่ำ 8 บิต (เงื่อนไขของระดับ $<8$) ยกเลิกการทำซ้ำ