Score:1

รหัสนี้คำนวณ AES S-Box ทำงานอย่างไร

ธง us

รหัสนี้คำนวณ AES S-Box ทำงานอย่างไร ฉันไม่เข้าใจขั้นตอนการคำนวณโดยรวม รหัสแนบด้านล่าง:

ฟังก์ชันสร้าง (irreducible_poly){
    พยายาม{
        p = parseInt(eval(irreducible_poly.replace(/x/g, '10')), 2);
    } จับ (ผิดพลาด) {
        console.log('พหุนามที่ลดไม่ได้ไม่ถูกต้อง');
        กลับ;
    }

    ให้ t = ใหม่ Uint32Array(256);
    สำหรับ (ให้ i = 0, x = 1; i < 256; i ++) {
        เสื้อ[i] = x;
        x ^= (x << 1) ^ ((x >>> 7) * p);
    }

    ให้ Sbox = ใหม่ Uint32Array(256);
    Sbox[0] = 0x63;
    สำหรับ (ให้ฉัน = 0; ฉัน <255; ฉัน ++) {
        ให้ x = เสื้อ[255 - ฉัน];
        x |= x << 8;
        x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
        Sbox[t[i]] = (x ^ 0x63) & 0xFF;
    }

    ส่งคืน Sbox;
}


// ผกผันของ Sbox
ฟังก์ชันผกผัน (sbox) {
    ให้ InvSbox = ใหม่ Uint32Array(256);
    สำหรับ (ให้ i = 0; i < 256; i++){
        InvSbox[i] = sbox.indexOf(i);
    }

    ส่งคืน InvSbox;
}
kelalaka avatar
in flag
อะไรไม่ชัดเจน? คุณลองด้วยมือหรือไม่? ดูตัวอย่างในเว็บไซต์ของเรา? คุณเห็นสิ่งนี้หรือไม่ http://www.moserware.com/assets/stick-figure-guide-to-advanced/A%20Stick%20Figure%20Guide%20to%20the%20Advanced%20Encryption%20Standard%20%28AES%29 ไฟล์ PDF
kelalaka avatar
in flag
สิ่งนี้ตอบคำถามของคุณหรือไม่ [วิธีคูณเลขฐานสิบหกใน GF(2^8)](https://crypto.stackexchange.com/questions/63139/how-to-do-hexadecimal-multiplication-in-gf28) คำถามนี้อาจเป็นคำถามหลอกลวง หรือ [ตารางการคูณ AES MixColumn เหล่านี้คำนวณอย่างไร](https://crypto.stackexchange.com/q/71204/18298) คุณช่วยระบุได้ไหมว่าสิ่งเหล่านั้นแก้ไขความสับสนของคุณ?
kelalaka avatar
in flag
คุณได้รับรหัสนี้ที่ไหน อาจมีคนเห็นรหัสนี้แล้ว แต่คุณช่วย [แก้ไข](https://crypto.stackexchange.com/posts/98396/edit) คำถามของคุณเพื่อระบุว่าคุณได้รับรหัสนี้จากที่ใดและแม้แต่ลิงก์ไปยังกระดาษได้หรือไม่ https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture8.pdf
us flag
https://merricx.github.io/aes-sbox/
us flag
คุณควรตรวจสอบองค์ประกอบเพื่อค้นหารหัส
ar flag
หวังว่าคุณจะไม่ป้อนอินพุตที่ไม่น่าเชื่อถือให้กับฟังก์ชัน "สร้าง" นั้น ;) ฉันคิดว่ามันไม่ได้แย่ขนาดนั้นตราบใดที่โค้ดรันบนฝั่งไคลเอนต์เท่านั้น เนื่องจากสิ่งที่คุณประนีประนอมได้ก็คือแซนด์บ็อกซ์ JS ของเบราว์เซอร์ ซึ่งผู้ใช้เบราว์เซอร์สามารถควบคุมได้อย่างเต็มที่ด้วยเครื่องมือ dev ถ้าเป็นสคริปต์ฝั่งเซิร์ฟเวอร์ล่ะก็â¦
Score:2
ธง ng

ภาพใหญ่: รหัสนี้จำเป็นต้องคำนวณโพลิโนเมียลโมดูโลไบนารีผกผัน $พี$ ของพหุนามเลขฐานสองที่ไม่ใช่ศูนย์ทุกตัว $R$ ระดับต่ำกว่าของ $พี$. ในการนี้ ได้เลือกการสร้างพหุนาม $G=1+x$และตาราง $Q_i=G^i\bmod P$ซึ่งเข้าถึงทุกสิ่งที่ต้องการ $R$. ผกผันการคูณของ $R=Q_i$ เป็น $Q_{255-i}$.


รหัสนี้ประเมิน AES S-box และมีค่าผกผันดังนี้:

  1. (บล็อกรหัสเริ่มต้นใน พยายาม) มันประเมิน p = 0x11b = 283 ที่แสดงถึงพหุนามไบนารี $P=1+x+x^3+x^4+x^8$ เป็นจำนวนเต็ม: ค่าที่ได้รับเมื่อประเมินพหุนามนี้สำหรับจำนวนเต็ม $x=2$. แบบแผนทั่วไปนี้ใช้ใน AES เพื่อจับคู่พหุนามไบนารีกับจำนวนเต็ม

  2. (บล็อกรหัสเริ่มต้นใน ให้ที) มันคำนวณตาราง 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.

  3. (บล็อกรหัสเริ่มต้นใน ให้ 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].

  4. (ฟังก์ชันผกผัน) ตารางผกผันคำนวณโดยการค้นหาแต่ละรายการในตาราง ใช้งานได้แต่ไม่มีประสิทธิภาพ 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$) ยกเลิกการทำซ้ำ

poncho avatar
my flag
$1+x$ ถูกใช้โดยเฉพาะเนื่องจาก $(1+x)^i \bmod P$ ถึงค่าทั้งหมด (นอกเหนือจาก 0) สำหรับ $i$ ระหว่าง 0 ถึง 254; คำศัพท์ทางเทคนิคที่เราใช้สำหรับสิ่งนี้คือ $1+x$ เป็น "ตัวสร้าง" ของฟิลด์นี้ (ในขณะที่คำง่ายๆ $x$ ไม่ใช่)
us flag
คุณช่วยอธิบายในแบบของคุณเองได้ไหม?? ฉันต้องการอัลกอริทึมนี้สำหรับงานวิทยานิพนธ์ของฉัน ที่จริงฉันเข้าใจว่าส่วนไหนสำหรับการคำนวณ แต่มันจะดีกว่าสำหรับฉันถ้าคุณอธิบายด้วยตัวอย่างเดียวแทนที่จะเป็นสมการ อีกด้วย; Sbox[t[i]] = (x ^ 0x63) & 0xFF; ทำไม FF ถึงใช้ที่นี่ คุณช่วยอธิบายหน่อยได้ไหม???
fgrieu avatar
ng flag
@Aktar1990: ฉันได้เพิ่มตัวอย่างที่เป็นตัวเลข รวมถึงหมายเหตุ 2 ที่อธิบายการแปลงที่ใกล้เคียงกัน รวมถึง `(x ^ 0x63) & 0xFF`สำหรับ `Sbox[t[i]]` มีคำอธิบายอยู่ใน "3"
us flag
@fgrieu คุณมีรหัสที่สมบูรณ์สำหรับ AES S-Box นี้พร้อมคำอธิบายที่ดีกว่าหรือไม่ ฉันแค่ต้องการการเข้ารหัสจากคุณ เมื่อฉันเรียกใช้ ฉันได้รับผลลัพธ์ ?? คุณมี ?? คุณรู้หรือไม่ว่าความซับซ้อนของเวลาและความซับซ้อนของพื้นที่ของ AES S-Box ??
fgrieu avatar
ng flag
@ Aktar1990: คุณเลือกรหัสนี้และเป็นภาษา ฉันไม่มีคำอธิบายที่ดีกว่านี้ หรือโค้ดที่มีความซับซ้อนของเวลาและพื้นที่ต่ำในทำนองเดียวกัน: `สร้าง' นั้นใกล้เคียงกับภาษาที่เหมาะสมที่สุดพอสมควร รหัสที่มีประสิทธิภาพใช้คณิตศาสตร์พหุนามและเทคนิคการเข้ารหัสที่ใช้เวลาและความพยายามในการทำความเข้าใจ แต่เนื่องจากคุณอยู่ในวิทยานิพนธ์ที่เกี่ยวข้อง คุณควรจะสามารถทำสิ่งนั้นได้
us flag
@fgrieu ตอนนี้ฉันเข้าใจขั้นตอนแล้ว ขอบคุณมาก

โพสต์คำตอบ

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