ตามวิกิพีเดีย:
https://th.wikipedia.org/wiki/Rijndael_S-box
AES กำลังทำสิ่งที่น่าสนใจ (ที่ $<<<$ เป็นวงกลม):
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
และนี่เท่ากับ ($\times$ กำลังทวีคูณเข้าไป $GF(2^8)$):
$s = b \คูณ 31 \mod 257$
นี่เป็นการผสมผสานที่ดีกับดวงตาของฉัน สมมติว่าฉันมี 128 บิต $x$ และ $y$ และฉันต้องการคำนวณสิ่งที่คล้ายกัน:
$x = y \oplus (y \lll 1) \oplus (y \lll 2) \oplus (y \lll 3) \oplus ... \oplus (y \lll 64)$
ฉันสามารถทำได้เร็วขึ้นโดยใช้การคูณใน $GF(2^{128}) \mod 2^{128}+1$? ฉันไม่รู้ทฤษฎีเบื้องหลังสิ่งนี้ ดังนั้นฉันจึงมีตัวคูณสองประเภทสำหรับสิ่งนี้:
$2^{125}-1$
และ
$2^{65}-1$
ฉันคิดว่าอันที่สองนี้อาจทำงานในลักษณะเดียวกัน $GF(2^{128})$นี่คือกฎมีหมายเลขที่คล้ายกันที่ฉันสามารถใช้ได้หรือไม่ ตัวเลขนั้นคืออะไร?
แก้ไข: ดูเหมือนว่ามีข้อผิดพลาดในบทความและการเลื่อนแบบวงกลมอาจเป็นไปในทิศทางอื่น:
$s = b \oplus (b \ggg 1) \oplus (b \ggg 2) \oplus (b \ggg 3) \oplus (b \ggg 4)$
อย่างไรก็ตาม เราสามารถสรุปได้หรือไม่? ในเอกสารนี้ไม่มีอะไรเกี่ยวกับความเท่าเทียมกันของการคูณ GF ของขั้นตอนนั้น:
https://csrc.nist.gov/csrc/media/publications/fips/197/final/documents/fips-197.pdf
ตกลง ปัญหาการเลื่อนซ้ายไปขวาเกี่ยวข้องกับหากตัวแปรแสดงด้วยแบบแผน "big-endian" หรือ "little-endian" เช่น ถ้าบิตที่มีนัยสำคัญน้อยที่สุดอยู่ทางซ้ายหรือขวา
การดำเนินการ:
$$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$$
เทียบเท่ากับการคูณ (โดยที่ shift คือ $\คูณ x$ ด้านล่าง)
$$ s(x)=b(x)(1+x+x^2+x^3+x^4)=b(x)\frac{x^5-1}{x-1} $$ แต่เนื่องจากการเลื่อนไปทางซ้ายก็เพิ่มขึ้นเป็นสองเท่าเช่นกัน $x=2,$ ที่จะได้รับ $s(x)=(2^5-1)b(x).$ ไม่ว่าในกรณีใด การเปลี่ยนแปลงตามรอบจะเทียบเท่ากับการทำงาน $\pmod x^n-1$ ที่ไหน $n$ คือความยาวของคำเป็นบิต
การดำเนินการที่สองของคุณเทียบเท่ากับการคูณด้วย $2^{65}-1.$
เนื่องจากคุณดูมีความสามารถทางคณิตศาสตร์เพียงพอ ฉันขอแนะนำ:
อ่านเอกสาร "ข้อเสนอ AES" โดย Daemen และ Rijmen ฉบับเต็มเพื่อทำความคุ้นเคยกับการดำเนินการและการเป็นตัวแทนประเภทนี้ มีหนังสือด้วย การออกแบบของ Rijndael โดยผู้เขียนคนเดียวกัน คุณกำลังเรียนรู้เกี่ยวกับความสัมพันธ์ระหว่าง Galois Fields ของคุณลักษณะ 2 $GF(2^n)$ และวงแหวนจำนวนเต็ม $\mathbb{Z}_{2^n-1}$ ซึ่งสามารถ "ย่อยสลาย" ได้ด้วย $\mathbb{Z}_{2^{n/2}-1} \times \mathbb{Z}_{2^{n/2}+1},$ เมื่อไร $n$ เท่ากันอีกที่หนึ่งที่ควรดูคือเอกสารเกี่ยวกับการออกแบบ SAFER-64 โดย Jim Massey โดยทั่วไปแล้วการแปลงเชิงทฤษฎีเชิงจำนวน (NTTs) ซึ่งสรุปการแปลงฟูริเยร์แบบเร็ว
หากคุณมี recursive decompositions ประเภทที่ฉันกล่าวถึงข้างต้น แสดงว่าคุณมีการใช้งานที่รวดเร็ว การแปลงที่ง่ายที่สุดคือเมทริกซ์ Sylvester Hadamard ที่ใช้ในการแปลง Fast Walsh-Hadamard โดยที่ $n$ ผลิตภัณฑ์โครเนกเกอร์ของเมทริกซ์เดียวกัน $H_2$ ถูกนำมาใช้: $$ H_n =H_2 \o ครั้ง H_2 \o ครั้ง \cdots \o ครั้ง H_2 $$ กับ $$ H_2=\left[\begin{array}{cc} +1 & +1 \ +1 & -1 \end{array} \right] $$ ตั้งแต่นี้เป็น เดอะ การแปลงฟูเรียร์สำหรับปริภูมิเวกเตอร์ไบนารี $GF(2)^n=\{0,1\}^n$ แถวของเมทริกซ์ Hadamard ด้านบนเป็นอักขระกลุ่มของกลุ่มการบวกของ $(\mathbb{GF(2)^n},\oplus)$ ทุกอย่างสมเหตุสมผล
อย่างไรก็ตามขอให้มีความสุขกับการอ่าน
มีบางอย่างที่ทำให้เข้าใจผิดในบทความ Wikipedia พวกเขาเขียน:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
เท่ากับ:
$s = b \คูณ 31 \mod 257$
ที่ไหน $\times$ คือการคูณพหุนามของ $ข$ และ $31$ นำมาเป็นบิตอาร์เรย์ แต่ $\mod 257$ ไม่ใช่การทำงานของโมดูโลมาตรฐาน แต่เป็น mod in $GF(2^8)$ และ $257$ เป็นจริงพหุนามของรูปแบบ $x^{9}+1$.
เราสามารถเห็นได้อย่างง่ายดายว่าการคูณของ $b \คูณ 31$ เท่ากับ:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
เป็นบิต $7,6,5,4$, ที่ไหน $\ll$ เป็นการเลื่อนระดับบิต ไม่ใช่การเลื่อนแบบวนรอบ แต่ในตัวอย่าง Wikipedia และใน AES มีการเลื่อนแบบวงกลม แล้ววงกลมมาจากไหน? มันมาจากการลดลงของพหุนาม $x^9+1$. นี่คือวิธีการคูณด้วยการลดพหุนาม $GF(2^8)$:
#รวม <cstdint>
#รวม <cstdio>
#รวม <บิตเซ็ต>
#รวม<iostream>
uint8_t ทวีคูณ (uint a, uint b)
{
uint8_t p = 1;
uint16_t L = 1;
uint16_t ค = 0;
สำหรับ (int i ที่ไม่ได้ลงชื่อ = 0; i < 8; ++i)
{
ค ^= ก & (L << i) ? (uint16_t)ข << ผม : 0;
}
สำหรับ (int ที่ไม่ได้ลงชื่อ i = 8; i-- > 0; )
{
ถ้า (c & (L << (i + 8)))
{
ค ^= L << (i + 8);
ค ^= (uint16_t)p << ผม;
}
}
กลับ (uint8_t)ค;
}
int หลัก ()
{
ผลลัพธ์ uint = 0;
ผลลัพธ์ = คูณ (131,31);
std::cout << ผลลัพธ์;
กลับ 0;
}
เราต้องการพหุนามดีกรี $9$แต่เราสามารถกำหนดพหุนามแบบลดขนาดในการใช้งานจริงได้โดยใช้เพียงตัวแรกเท่านั้น $8$ บิตที่มีนัยสำคัญน้อยที่สุด ดังนั้นในกรณีของเรา $p=1$. ตอนนี้ถ้าเราดูว่าการคูณแบบไม่มีพกพาทำงานอย่างไร (ลูปแรก) เราจะเห็นว่า $7,6,5,4$ บิตเราจะได้ผลลัพธ์เดียวกันกับ shift:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
แต่แทนที่บิต $11,10,9,8$ จะมีการเลื่อนบิต (ยกเลิก) อย่างแน่นอนในกระบวนการเปลี่ยนระดับบิต นี่เป็นเพราะการคูณแบบไม่ใช้การพกพาจะย้ายพวกมันไปทางซ้าย $1,2,3...$ ตำแหน่งแล้วทั้งหมดจะถูก xored ชอบที่นี่:
เนื่องจากเรากำลังคูณด้วย $31$ เราจะได้รับเสมอ $4$ บิตพิเศษในครึ่งที่มีนัยสำคัญสูงกว่าของผลลัพธ์ 16 บิตของเรา และพวกเขาจะต้องเสียใจ เพราะนี่คือวิธีการทำงานของการคูณแบบไม่พก ตอนนี้เรามีบิต $7,6,5,4$ เท่ากับผลลัพธ์ของ:
$s = b \oplus (b \ll 1) \oplus (b \ll 2) \oplus (b \ll 3) \oplus (b \ll 4)$
และบิต $11,10,9,8$ซึ่งอาจใช้แทนบิต $3,2,1,0$. ในการเลื่อนแบบวงกลม เราจำเป็นต้อง xor กลับบิตนี้เท่านั้น สิ่งนี้ทำได้โดย:
สำหรับ (int ที่ไม่ได้ลงชื่อ i = 8; i-- > 0; )
{
ถ้า (c & (L << (i + 8)))
{
ค ^= L << (i + 8);
ค ^= (uint16_t)p << ผม;
}
}
ถ้า $p=1$. เราจะเห็นว่ารหัสนี้กำลังตรวจสอบว่ามีบิตเท่ากับหรือไม่ $1$ ด้านซ้ายบนตำแหน่ง $i$ ของครึ่งบนของเรา และถ้าเป็นเช่นนั้น มันก็จะ xor บิตนั้นด้วยบิต $i$ ในครึ่งล่างของเรา และอัลกอริทึมทั้งหมดนั้นก็เท่ากับ xoring กับ circialr shift $\llll$:
$s = b \oplus (b \lll 1) \oplus (b \lll 2) \oplus (b \lll 3) \oplus (b \lll 4)$
เมื่อรู้สิ่งนี้จะเห็นได้ชัดว่าความเท่าเทียมกันประเภทนี้มีไว้สำหรับสิ่งใดก็ตาม $GF(2^k)$, ให้เราเลือก $p=1$ (ตามแบบแผนของรหัสที่โพสต์) เป็นพหุนามและตัวคูณของเราเท่ากับ $2^{\frac {k}{2}+1}+1$.
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
