การคูณ/การหารไม่ถูกต้องในสนาม Galois (2^8)

ฉันกำลังพยายามใช้การคูณและการหารใน GF(2^8) โดยใช้ตารางบันทึกและเลขชี้กำลัง ฉันใช้เลขชี้กำลังของ 3 เป็นตัวสร้าง โดยใช้คำแนะนำจาก ที่นี่< /ก>.

อย่างไรก็ตาม ฉันไม่ผ่านกรณีทดสอบเล็กน้อยบางกรณี

ตัวอย่าง:

//passes  
assert((GF256elm(4) / GF256elm(1)) == GF256elm(4));  
assert((GF256elm(32) / GF256elm(16)) == GF256elm(2));  
assert((GF256elm(15) / GF256elm(5)) == GF256elm(3));  
assert((GF256elm(88) / GF256elm(8)) == GF256elm(11));  
//fails, but should pass
assert((GF256elm(77) / GF256elm(11)) == GF256elm(7));
assert((GF256elm(77) / GF256elm(7)) == GF256elm(11));

สี่บรรทัดแรกผ่านไป อย่างไรก็ตาม มันล้มเหลวทั้งบนบรรทัดที่ 5 และ 6
จากการตรวจสอบเพิ่มเติม ฉันพบว่าข้อผิดพลาดเหล่านี้เกิดขึ้นเมื่อมี 'wrap over' เช่น log3(a) + log3(b) > 255 (ตัวคูณ) หรือ log3(a) - log3(b) < 0 อย่างไรก็ตาม ค่าจะถูกดัดแปลงเพื่อให้คงอยู่ใน 0~255 โดยใช้โมดูลัสจริง

GF256elm& GF256elm::operator/=(const GF256elm& other) { //C++ operator override for division
    int t = _logTable[val] - _logTable[other.val]; //log3(a) - log3(b)
    int temp =  ((t % 255) + 255) % 255; //this wraps the value to between 0~254 inclusive.
    val = _expTable[temp];
    return *this;
}

ตัวดำเนินการ / ถูกนำมาใช้โดยใช้การแทนที่ /= ด้านบน ดังนั้นจึงไม่มีอะไรพิเศษเกิดขึ้นที่นั่น

ฉันได้ตรวจสอบแล้วว่าตารางบันทึก/exp ที่สร้างขึ้นนั้นถูกต้อง

ฉันพลาดอะไรไปที่นี่? ขอบคุณ!


c++ cryptography galois-field
person Jacob Wang    schedule 25.08.2013    source แหล่งที่มา
comment
ขอโทษด้วย. ใช่ ฉันได้ดำเนินการแล้วและควรจะกล่าวถึงมัน โดยพื้นฐานแล้วจะใช้เพียง /= กับเงื่อนไข LHS และ RHS แล้วส่งคืนผลลัพธ์ดังนั้นจึงไม่มีอะไรพิเศษ แก้ไขคำตอบของฉัน   -  person Jacob Wang    schedule 25.08.2013

คำตอบ (3)


arrow_upward
4
arrow_downward

ขั้นแรก อ่านคำถามนี้ รวมถึงคำตอบและความคิดเห็นทั้งหมดอย่างละเอียด:

การบวกและการคูณในฟิลด์ Galois

ฉันคิดว่ารหัสของคุณใช้ได้ แต่คุณมีปัญหาสองประการ

ประการแรกความคิดเห็นนั้นผิด คุณกำลังรักษาเลขชี้กำลังให้อยู่ในช่วง 0-254 ไม่ใช่ 0-255

ประการที่สอง กรณีทดสอบ "เล็กน้อย" ของคุณไม่ถูกต้อง

ในสาขานี้ ให้คิดว่าตัวเลขคือพหุนามซึ่งคุณจะได้ค่าสัมประสิทธิ์จากการแทนค่าเลขฐานสอง ตัวอย่างเช่น เนื่องจาก 5 = 2^2 + 1 ในช่องนี้ "5" หมายถึง x^2 + 1

ดังนั้น "5" * "3" = (x^2 + 1) * (x + 1) = x^3 + x^2 + x + 1 หรือ "15" นี่คือเหตุผลที่กรณีทดสอบของคุณ assert((GF256elm(15) / GF256elm(5)) == GF256elm(3)); ทำงาน มันไม่เกี่ยวอะไรกับความคิดปกติของคุณที่ว่าห้าคูณสามเท่ากับสิบห้า ในทำนองเดียวกันสำหรับกรณีทดสอบการทำงานอื่นๆ ของคุณ ซึ่งคุณจะสังเกตเห็นว่าส่วนใหญ่เกี่ยวข้องกับการยกกำลังสอง

อย่างไรก็ตาม "7" * "11" = (x^2 + x + 1) * (x^3 + x + 1) = x^5 + x^4 + 2x^3 + 2x^2 +2x + 1

แต่สัมประสิทธิ์เป็นโมดูโล 2 ทั้งหมด ดังนั้นนี่คือ x^5 + x^4 + 1 = "49" นี่คือสาเหตุที่กรณีทดสอบสองกรณีล่าสุดของคุณล้มเหลว

หากคุณลอง assert(GF256elm(49) / GF256elm(7) == GF256elm(11)); คุณควรจะพบว่าได้ผล

person Nemo    schedule 26.08.2013
comment
ฉันรู้ (และตั้งใจ) วางไว้ในช่วง 0~254 ตามที่อธิบายไว้ในความคิดเห็นของฉัน ขอบคุณที่อธิบายแนวคิดเรื่องการคูณในสนามจำกัด ฉันได้วางกรณีทดสอบที่ไม่ดีลงจริงๆ เนื่องจากฉันขาดความเข้าใจในสาขาที่มีขอบเขตจำกัด - person Jacob Wang; 26.08.2013
comment
@jtcwang แต่ความคิดเห็นใน รหัส ของคุณบอกว่า //this wraps the value to between 0~255 - person gx_; 26.08.2013
comment
จะแก้ไข ขอบคุณสำหรับการพบเห็น - person Jacob Wang; 06.09.2013

arrow_upward
0
arrow_downward

x % n ประเมินเป็นจำนวนเต็มระหว่าง 0 ถึง (n - 1) รวมอยู่ด้วย

ซึ่งหมายความว่า x % 255 ประเมินเป็นจำนวนเต็มระหว่าง 0 ถึง 254 ไม่ใช่ 0 ถึง 255

คุณควรแทนที่ 255 ด้วย 256 หรืออีกทางหนึ่ง ให้ดำเนินการระดับบิต AND ด้วย 0xff เพื่อให้ได้ผลลัพธ์เดียวกัน อย่างหลังนั้นเร็วกว่าแม้ว่าจะมีความเป็นไปได้ค่อนข้างมากที่คอมไพเลอร์จะฉลาดพอที่จะปรับให้เข้ากับไบต์โค้ดเดียวกันได้

person ntoskrnl    schedule 25.08.2013
comment
อย่างไรก็ตาม สิ่งนี้เป็นจริงไม่เพียงแต่สำหรับ C++ % แต่สำหรับการหารจำนวนเต็ม (โมดูโล) โดยทั่วไป ความแม่นยำ: เมื่อมีการลงชื่อ x (เช่น int x) x % 255 สามารถประเมินเป็นจำนวนเต็มระหว่าง -254 ถึง 254 (รวม) (นั่นคือสาเหตุที่โค้ดของ OP เป็น ((t % 255) + 255) % 255 และไม่ใช่แค่ t % 255) - person gx_; 25.08.2013
comment
ฉันเคยลองแล้ว แต่มันก็ไม่ได้ผล ด้วยความเข้าใจอันจำกัดของฉันเกี่ยวกับ GF(2^8) รูปแบบของตาราง exp/log จะเกิดซ้ำในองค์ประกอบที่ 255 กล่าวคือ องค์ประกอบ [1] เหมือนกับ [255] จึงทำให้เกิดโมดูลัส 255 - person Jacob Wang; 25.08.2013

arrow_upward
0
arrow_downward

ไม่มีอะไรผิดปกติกับรหัส การคูณ/หารฟิลด์จำกัดแตกต่างจากเลขคณิตปกติ โปรดดูคำถามนี้ใน cryptostackxchange

person Jacob Wang    schedule 26.08.2013