การลงทะเบียนการเปลี่ยนแปลงความคิดเห็นเชิงเส้น Linear Shift Register พร้อมคำติชม ตัวอย่าง Linear Shift Register

ในการสร้าง stream ciphers มักจะใช้ซีเควนซ์บน shift register การลงทะเบียนกะผลป้อนกลับประกอบด้วยสองส่วน: การลงทะเบียนกะและฟังก์ชันป้อนกลับ ดังแสดงในรูปที่ 87. shift register นั้นเป็นลำดับของบิตซึ่งจำนวนที่กำหนดความยาวของรีจิสเตอร์ ดังนั้นถ้า n บิตเกี่ยวข้องกับรีจิสเตอร์ก็บอกว่ารีจิสเตอร์ n-bit shift ทุกครั้งที่มีการดึงข้อมูลบิต บิตทั้งหมดของ shift register จะถูกเลื่อนไปทางขวาหนึ่งตำแหน่ง โดยปกติแล้วจะไปยังบิตที่มีนัยสำคัญน้อยที่สุด ระยะเวลาของ shift register คือความยาวของลำดับผลลัพธ์ก่อนที่จะเริ่มทำซ้ำ

ข้าว. 87.

ฟังก์ชันทางคณิตศาสตร์ใดๆ ที่ดำเนินการกับบิตสามารถทำหน้าที่เป็นผลป้อนกลับได้ ชนิดที่ง่ายที่สุดของการลงทะเบียนกะผลป้อนกลับคือการลงทะเบียนการเปลี่ยนแปลงผลป้อนกลับเชิงเส้น (LFSR) ใน LFSR คำติชมเป็นเพียงการดำเนินการเพิ่มโมดูโล 2 (XOR) ในบางบิตของรีจิสเตอร์ รายการของบิตเหล่านี้เรียกว่าลำดับของก๊อกหรือจุดรับดังแสดงในรูปที่ 88. บางครั้งรูปแบบดังกล่าวเรียกว่าการกำหนดค่าฟีโบนักชี เนื่องจากความเรียบง่ายของลำดับผลป้อนกลับ จึงสามารถใช้ทฤษฎีทางคณิตศาสตร์ที่พัฒนาอย่างเป็นธรรมเพื่อวิเคราะห์ LFSR ได้ ไม่ว่าในกรณีใด คุณภาพของ SRP ที่ผลิตขึ้นจะถูกประเมินโดยชุดการทดสอบพิเศษ

ข้าว. 88.

LFSR เขียนในรูปของพหุนาม ในกรณีนี้ ระดับขององค์ประกอบแรกของพหุนามระบุจำนวนบิตในการลงทะเบียนกะ และเลขชี้กำลังของสมาชิกที่เหลือของพหุนามบ่งชี้ว่าจะใช้จุดรับใด ตัวอย่างเช่น การเขียน x 4 + x + 1 หมายความว่าจะใช้รีจิสเตอร์ขององค์ประกอบสี่ตัว ซึ่งบิต bi และ b 0 จะมีส่วนร่วมในการก่อตัวของข้อเสนอแนะ (รูปที่ 89)

ข้าว. 89.4

พิจารณาการทำงานของรีจิสเตอร์ที่แสดงในรูปที่ 89. เริ่มต้นมันด้วยค่า 0101 (การเริ่มต้นเริ่มต้นสามารถทำได้โดยลำดับของบิตใด ๆ ยกเว้นลำดับของศูนย์เท่านั้นเนื่องจากในกรณีนี้ข้อเสนอแนะจะสร้างค่าเป็นศูนย์เสมอและการลงทะเบียนจะ ไม่ได้ผลิต PSP ที่คาดไว้) ดังนั้นในทะเบียนจะมีการเลื่อนไปทางขวาหนึ่งตำแหน่ง บิตที่มีนัยสำคัญน้อยที่สุดเท่ากับ 1 ถูกบังคับให้ออกจากรีจิสเตอร์และสร้างบิตแรกของ PRS บิตเหล่านั้นที่อยู่ในตำแหน่ง b และ b 0 ก่อนกะจะถูกเพิ่มโมดูโล 2 และสร้างใหม่

บิตสูงของการลงทะเบียน ตัวอย่างของการดำเนินการของ LFSR ที่พิจารณาจะแสดงในรูปที่ 90.

ข้าว. 90.

ดังจะเห็นได้จากรูปที่ 90 การกรอกทะเบียนจะผ่านน้ำหนัก 15 จาก 16 รัฐที่เป็นไปได้ (ก่อนหน้านี้เรากำหนดว่ารัฐที่สิบหกเมื่อ LFSR เป็น 0000 ไม่สามารถพิจารณาได้) หลังจากนั้นการเติมรีจิสเตอร์จะเท่ากับค่าเริ่มต้นที่ 0101 อีกครั้งและการสร้างลำดับบิตจะเริ่มทำซ้ำ ลำดับเอาต์พุตของรีจิสเตอร์จะเป็นสตริงของบิตที่มีนัยสำคัญน้อยที่สุด (จนถึงเส้นแนวนอนในรูปที่ 90): 101011110001001 ขนาดของลำดับบิตก่อนทำซ้ำเรียกว่าคาบ เพื่อให้แน่ใจว่าระยะเวลาสูงสุดของ LFSR เฉพาะ (เช่น เพื่อให้รีจิสเตอร์ผ่านสถานะภายในที่เป็นไปได้ทั้งหมด) พหุนามที่กำหนดการทำงานของรีจิสเตอร์จะต้องเป็นโมดูโลดั้งเดิม 2 เช่นเดียวกับจำนวนเฉพาะขนาดใหญ่ ไม่มีทาง สร้างพหุนามดังกล่าว เราสามารถใช้พหุนามและตรวจสอบว่าเป็นโมดูโล 2 ที่ลดไม่ได้หรือไม่ ในกรณีทั่วไป พหุนามดึกดำบรรพ์ของดีกรี n เป็นพหุนามที่ลดทอนไม่ได้ซึ่งเป็นตัวหารของ x 2 "+1 แต่ไม่ใช่ตัวหารของ xd +1 สำหรับ d ทั้งหมดที่เป็นตัวหารของ 2 "-1 B. Schneier จัดทำตารางพหุนามบางตัวซึ่งเป็นโมดูโล 2 ที่ลดไม่ได้

สรุปความรู้ที่ได้รับจากการพิจารณาตัวอย่างการทำงานของ LFSR (รูปที่ 90) เราสามารถพูดได้ว่า n-bit LFSR สามารถอยู่ในสถานะภายใน 2”-1 อย่างใดอย่างหนึ่ง ในทางทฤษฎี รีจิสเตอร์ดังกล่าวสามารถสร้างลำดับสุ่มหลอกด้วยคาบ 2 n -1 บิต การลงทะเบียนดังกล่าวเรียกว่าการลงทะเบียน LFSR โดยมีระยะเวลาสูงสุด ผลลัพธ์ที่ได้เรียกว่าลำดับที

กระทรวงศึกษาธิการและวิทยาศาสตร์

มหาวิทยาลัยสังคมแห่งรัฐรัสเซีย

คณะเทคโนโลยีสารสนเทศ

กรมคุ้มครองข้อมูล

วิธีการเข้ารหัสและวิธีการรับรองความปลอดภัยของข้อมูล

หลักสูตรการทำงาน

“ร shift registers พร้อมการป้อนกลับเชิงเส้นเป็นตัวสร้างตัวเลขสุ่มหลอก"

สมบูรณ์:

นักศึกษาชั้นปีที่ 3

กลุ่ม KZOI-D-3

Larionov I.P.

ตรวจสอบแล้ว:

รศ. บาราโนวา อี.เค.

มอสโก 2011
เนื้อหา

บทนำ ……………………………..…………………………………….3

1. รากฐานทางทฤษฎีของการทำงาน…………………………………………4
   1. ข้อมูลทั่วไปเกี่ยวกับการลงทะเบียนกะผลตอบรับ…………..4
      1. เกี่ยวกับการเข้ารหัสสตรีมตาม RgCsLOS……….…………10
      2. ความซับซ้อนเชิงเส้นของลำดับสุ่มหลอกที่สร้างขึ้น PgCsLOS…………………………………….……12
      3. เกี่ยวกับความเป็นอิสระสหสัมพันธ์ของลำดับที่สร้างขึ้นของตัวเลขสุ่มหลอก PrCsLOS………..13
      4. เกี่ยวกับวิธีการอื่นในการเปิดลำดับที่สร้างขึ้นของตัวเลขสุ่มหลอก RgCsLOS……………………………………..14
2. การใช้ซอฟต์แวร์ของ RgCsLOS เป็นตัวสร้างลำดับสุ่มหลอก….…………………………….15
   1. โครงร่างทั่วไปของอัลกอริทึม……………………………………...15
   2. คำอธิบายของโมดูลซอฟต์แวร์และอินเทอร์เฟซ…….16
   3. คู่มือผู้ใช้…………………………………………………… 20

บทสรุป ………………………………………………………………22

บรรณานุกรม………………………………………………….....23

ภาคผนวก A ….………………………………………………………..24

การแนะนำ

จุดประสงค์ของงานนี้คือเพื่อพัฒนาแอพพลิเคชั่นซอฟต์แวร์ที่ใช้การทำงานของตัวสร้างตัวเลขสุ่มหลอกโดยอิงจากการลงทะเบียนกะพร้อมผลตอบรับ การพัฒนาแอปพลิเคชันนี้ด้วยอินเทอร์เฟซแบบกราฟิกดำเนินการในภาษา C++ สำหรับระบบปฏิบัติการ Windows

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

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

1. รากฐานทางทฤษฎีของงาน

1.1 ข้อมูลทั่วไปเกี่ยวกับการลงทะเบียนกะพร้อมคำติชมเชิงเส้น

ลำดับการลงทะเบียน Shift ใช้ในทฤษฎีการเข้ารหัสและการเข้ารหัส ทฤษฎีของพวกเขาได้รับการพัฒนามาอย่างดี การเข้ารหัสสตรีมแบบลงทะเบียนกะทำงานเป็นกลไกหลักในการเข้ารหัสทางการทหารมานานก่อนการถือกำเนิดของอุปกรณ์อิเล็กทรอนิกส์

การลงทะเบียนกะผลตอบรับ (ต่อไปนี้จะเรียกว่า PgCsOS) ประกอบด้วยสองส่วน: การลงทะเบียนกะและฟังก์ชันป้อนกลับshift register เป็นลำดับของบิต กำหนดจำนวนบิตเปลี่ยนความยาวของรีจิสเตอร์ถ้าความยาวเป็น n บิต รีจิสเตอร์จะเรียกว่าการลงทะเบียนกะ n-bit. เมื่อใดก็ตามที่จำเป็นต้องแยกบิต บิตทั้งหมดของ shift register จะถูกเลื่อนไปทางขวา 1 ตำแหน่ง บิตซ้ายสุดใหม่เป็นฟังก์ชันของบิตอื่นๆ ทั้งหมดในรีจิสเตอร์ ผลลัพธ์ของ shift register เป็นหนึ่งบิตซึ่งมักจะมีความสำคัญน้อยที่สุดระยะเวลาลงทะเบียนกะคือความยาวของลำดับผลลัพธ์ก่อนที่จะเริ่มทำซ้ำ

รูปข้อเสนอแนะ Shift Register

การลงทะเบียน Shift พบการใช้งานอย่างรวดเร็วในการเข้ารหัสสตรีม เนื่องจากใช้งานได้ง่ายโดยใช้ฮาร์ดแวร์ดิจิทัล ในปี 1965 Ernst Selmer หัวหน้าผู้เข้ารหัสของรัฐบาลนอร์เวย์ ได้พัฒนาทฤษฎีลำดับ shift register โซโลมอน โกลอมบ์ นักคณิตศาสตร์ของ NSA เขียนหนังสือสรุปผลงานบางส่วนของเขาและผลงานของเซลเมอร์ การลงทะเบียนกะผลป้อนกลับแบบง่ายที่สุดคือการลงทะเบียนการเปลี่ยนแปลงความคิดเห็นเชิงเส้น (การลงทะเบียนการเปลี่ยนแปลงความคิดเห็นเชิงเส้น ซึ่งต่อไปนี้จะเรียกว่า LFSR หรือ RgCsLOS) . ข้อเสนอแนะของรีจิสเตอร์ดังกล่าวเป็นเพียง XOR (โมดูโลสองเพิ่มเติม) ของบิตของรีจิสเตอร์ รายการของบิตเหล่านี้เรียกว่าลำดับการแตะ บางครั้งการลงทะเบียนดังกล่าวเรียกว่าการกำหนดค่าฟีโบนักชี เนื่องจากความเรียบง่ายของลำดับผลป้อนกลับ ทฤษฎีทางคณิตศาสตร์ที่ค่อนข้างพัฒนาจึงสามารถนำมาใช้วิเคราะห์ PgCsLOC ได้ ด้วยการวิเคราะห์ลำดับเอาต์พุตที่เป็นผลลัพธ์ คุณสามารถตรวจสอบว่าลำดับเหล่านี้เป็นแบบสุ่มเพียงพอที่จะปลอดภัยหรือไม่ Shift register ถูกใช้บ่อยกว่า shift register อื่นๆ ในการเข้ารหัส

รูป PgCsLOS Fibbonacci

โดยทั่วไป n -bit PrCsLOS สามารถเป็นหนึ่งใน N=2n -1 สถานะภายใน ซึ่งหมายความว่า ตามทฤษฎีแล้ว รีจิสเตอร์ดังกล่าวสามารถสร้างลำดับสุ่มหลอกด้วยช่วงเวลา T=2น -1 บิต (จำนวนสถานะภายในและระยะเวลาเท่ากัน N=Tmax=2n -1 เนื่องจากการเติม PrCsLOC ด้วยศูนย์จะทำให้ shift register ส่งออกลำดับศูนย์ที่ไม่สิ้นสุด ซึ่งไม่มีประโยชน์อย่างยิ่ง) เฉพาะกับลำดับการแตะบางอย่างเท่านั้น PrCsLOS จะส่งผ่าน 2 . ทั้งหมดเป็นวงจรน -1 สถานะภายใน RgCsLOS ดังกล่าวคือRgSsLOS ที่มีระยะเวลาสูงสุด. ผลลัพธ์ที่ได้เรียกว่าM-ลำดับ.

ตัวอย่าง . รูปด้านล่างแสดง PrCsLOS 4 บิตโดยแตะจากบิตที่หนึ่งและสี่ หากเริ่มต้นด้วยค่า 1111 ก่อนที่จะทำซ้ำการลงทะเบียนจะใช้สถานะภายในต่อไปนี้:

Shift ขีดหมายเลข (สถานะภายใน)	สถานะการลงทะเบียน				บิตเอาต์พุต
ค่าเริ่มต้น
15 (กลับสู่สถานะเริ่มต้น)
16 (สถานะซ้ำ)

ลำดับเอาต์พุตจะเป็นสตริงของบิตที่มีนัยสำคัญน้อยที่สุด: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 โดยมีจุด T=15 จำนวนรวมของสถานะภายในที่เป็นไปได้ (ยกเว้นศูนย์) N=2 4 -1=16-1=15= Tmax ดังนั้นลำดับเอาต์พุตคือเอ็ม -ลำดับ.

เพื่อให้ PgCsLOS เฉพาะมีคาบสูงสุด พหุนามที่เกิดขึ้นจากลำดับการต๊าปและค่าคงที่ 1 ต้องเป็นโมดูโลดั้งเดิม 2 พหุนามจะแสดงเป็นผลรวมของกำลัง ตัวอย่างเช่น พหุนามของดีกรีน ปรากฏดังนี้:

anxn +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =anxn +a n-1 x n-1 +…+a 1 x+a 0 , โดยที่ i =(0, 1 ) สำหรับ i=1…n, axi – หมายถึงบิต

ดีกรีของพหุนามคือความยาวของรีจิสเตอร์กะ พหุนามดั้งเดิมของดีกรี n คือพหุนามลดทอนที่เป็นตัวหารของ x 2n-1 +1 แต่ไม่ใช่ตัวหารของ x d +1 สำหรับ d ทั้งหมดเป็นตัวหารของ2น -หนึ่ง. ทฤษฎีทางคณิตศาสตร์ที่เกี่ยวข้องสามารถพบได้ใน

โดยทั่วไป ไม่มีวิธีง่ายๆ ในการสร้างพหุนามดั้งเดิมของดีกรีโมดูโล 2 วิธีที่ง่ายที่สุดคือการเลือกพหุนามโดยการสุ่มและตรวจสอบว่าพหุนามพหุนามเป็นพหุนามหรือไม่ ไม่ใช่เรื่องง่ายและคล้ายกับการตรวจสอบว่าตัวเลขที่เลือกแบบสุ่มเป็นจำนวนเฉพาะหรือไม่ แต่ชุดซอฟต์แวร์ทางคณิตศาสตร์จำนวนมากสามารถแก้ปัญหานี้ได้

บางพหุนามที่มีดีกรีต่างๆ แบบโมดูโล 2 ดั้งเดิม แต่ไม่แน่นอนทั้งหมด แสดงไว้ด้านล่าง ตัวอย่างเช่น รายการ

(32, 7, 5, 3, 2, 1, 0) หมายความว่าพหุนามต่อไปนี้เป็นโมดูโลดั้งเดิม 2: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

ซึ่งสามารถนำไปสรุปเป็น PrCcLOC ได้อย่างง่ายดายด้วยระยะเวลาสูงสุด ตัวเลขแรกคือความยาวของ PrCsLOS ตัวเลขสุดท้ายเป็น 0 เสมอและสามารถละเว้นได้ ตัวเลขทั้งหมดยกเว้น 0 ระบุลำดับการแตะ นับจากขอบด้านซ้ายของการลงทะเบียนกะ นั่นคือ เงื่อนไขของพหุนามที่มีดีกรีต่ำกว่าจะสัมพันธ์กับตำแหน่งที่ใกล้กับขอบด้านขวาของรีจิสเตอร์

ต่อจากตัวอย่าง การเขียน (32, 7, 5, 3, 2, 1, 0) หมายความว่าสำหรับการลงทะเบียนกะ 32 บิตที่กำหนด บิตใหม่จะถูกสร้างขึ้นโดย XORing สามสิบวินาที, เจ็ด, ห้า, สาม, วินาที และบิตแรก ผลลัพธ์ RgCsLOS จะมีความยาวสูงสุด วนซ้ำจนกว่าจะซ้ำ 2 32 -1 ค่า

รูปที่ 4 PrCsLOS 32 บิตที่มีความยาวสูงสุด

พิจารณารหัสโปรแกรม PgCsLOS ซึ่งลำดับการแตะมีลักษณะเป็นพหุนาม (32, 7, 5, 3, 2, 1, 0) ในภาษา C จะมีลักษณะดังนี้:

int LFSR()(

ShiftRegister แบบยาวที่ไม่ได้ลงชื่อคงที่ = 1;

/* ทั้งหมดยกเว้น 0 */

ShiftRegister = ((((ShiftRegister >> 31))

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^กะลงทะเบียน))

& 0x00000001)

<<31)

| (ShiftRegister >> 1 ;

ส่งคืน ShiftRegister & 0 x 00000001;)

หาก shift register ยาวกว่าคำในคอมพิวเตอร์ รหัสจะซับซ้อนมากขึ้น แต่ไม่มากนัก ในใบสมัครบี ตารางของพหุนามดั้งเดิมบางโมดูโล 2 ให้มา เราจะใช้มันในภายหลังเพื่อระบุคุณสมบัติบางอย่างของพหุนามเหล่านี้ เช่นเดียวกับในการใช้งานซอฟต์แวร์เพื่อกำหนดลำดับการแตะ

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

ถ้า p(x) เป็นพื้นฐาน ดังนั้น x . ก็คือน p(1/x) ดังนั้นแต่ละองค์ประกอบของตารางจึงกำหนดพหุนามดั้งเดิมสองตัว ตัวอย่างเช่น ถ้า (a, b, 0) เป็นพื้นฐาน มันก็จะเป็นเช่นนั้น (a, a-b, 0) ถ้า (a, b, c, d, 0) เป็นพื้นฐาน ก็เป็นเช่นนั้น (a, a-d, a-c, a-b, 0) ทางคณิตศาสตร์:

ถ้า x เป็นพื้นฐาน a+xb +1 แล้วมันเป็นดั้งเดิมและ x a+x a-b+1,

ถ้า x เป็นพื้นฐาน a + x b + x c + x d +1 แล้วมันเป็นดั้งเดิมและ x a + x a-d + x a-c + x a-b +1 trinomials ดั้งเดิมนั้นเร็วที่สุดในการติดตั้งโดยทางโปรแกรม เนื่องจากในการสร้างบิตใหม่ คุณต้อง XOR เพียงสองบิตของ shift register (ไม่คำนึงถึงระยะศูนย์เช่น x 0 =1 ดูตัวอย่างด้านบน) อันที่จริง พหุนามป้อนกลับทั้งหมดที่ให้ไว้ในตารางนั้นเบาบาง กล่าวคือ พวกมันมีค่าสัมประสิทธิ์เพียงเล็กน้อย Sparsity มักเป็นที่มาของความอ่อนแอ ซึ่งบางครั้งก็เพียงพอที่จะเปิดอัลกอริทึมได้ สำหรับอัลกอริธึมการเข้ารหัส จะดีกว่ามากถ้าใช้พหุนามดึกดำบรรพ์ที่มีสัมประสิทธิ์จำนวนมาก โดยใช้พหุนามหนาแน่น โดยเฉพาะอย่างยิ่งเป็นส่วนหนึ่งของคีย์ เราสามารถใช้ PrCcLOC ที่สั้นกว่าได้มาก

การสร้างพหุนามดั้งเดิมหนาแน่น modulo 2 ไม่ใช่เรื่องง่าย ในกรณีทั่วไป ในการสร้างพหุนามดึกดำบรรพ์ของดีกรี k เราจำเป็นต้องทราบการแยกตัวประกอบของจำนวน 2เค-1.

ด้วยตัวของมันเอง PgCsLOS เป็นตัวสร้างลำดับสุ่มหลอกที่ดี แต่พวกมันมีคุณสมบัติที่ไม่สุ่ม (กำหนดขึ้นเอง) ที่ไม่ต้องการ บิตตามลำดับเป็นแบบเส้นตรง ทำให้ไม่มีประโยชน์สำหรับการเข้ารหัส สำหรับ PgCsLOS ที่มีความยาว n สถานะภายในคือบิตเอาต์พุต n ก่อนหน้าของเครื่องกำเนิดไฟฟ้า แม้ว่ารูปแบบข้อเสนอแนะจะถูกเก็บเป็นความลับ แต่ก็สามารถกำหนดได้จากบิตเอาต์พุต 2n ของเครื่องกำเนิดไฟฟ้าโดยใช้อัลกอริธึม Berlekamp-Massey ที่มีประสิทธิภาพสูง

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

1.2 เกี่ยวกับรหัสสตรีมตาม RgCsLOS

แนวทางพื้นฐานในการออกแบบเครื่องกำเนิดคีย์สตรีมที่ใช้ PrCsLOS นั้นง่ายมาก ขั้นแรก ให้ใช้ PrCsLOS อย่างน้อยหนึ่งรายการ โดยปกติมีความยาวต่างกันและพหุนามป้อนกลับที่แตกต่างกัน (หากความยาวเป็น coprime และพหุนามป้อนกลับทั้งหมดเป็นแบบดั้งเดิม ตัวสร้างผลลัพธ์จะมีความยาวสูงสุด) กุญแจสำคัญคือสถานะเริ่มต้นของการลงทะเบียน PrCcLOC ทุกครั้งที่ต้องการบิตใหม่ ให้เปลี่ยนการลงทะเบียน PrCsLOS เล็กน้อย (บางครั้งเรียกว่าการตอกบัตร) บิตเอาท์พุตเป็นฟังก์ชัน โดยเฉพาะอย่างยิ่ง ไม่เป็นเชิงเส้น ของบิตบางบิตของการลงทะเบียน PrCsLOC ฟังก์ชันนี้เรียกว่าฟังก์ชันการรวม และตัวสร้างโดยรวมเรียกว่าตัวสร้างเชิงผสม (หากบิตเอาต์พุตเป็นฟังก์ชันของ PgCsLOS ตัวเดียว ออสซิลเลเตอร์จะเรียกว่าออสซิลเลเตอร์ตัวกรอง) ทฤษฎีส่วนใหญ่ที่อยู่เบื้องหลังอุปกรณ์ประเภทนี้ได้รับการพัฒนาโดย Selmer และ Neal Zierler คุณสามารถทำให้เกิดภาวะแทรกซ้อนได้หลายอย่าง ในเครื่องกำเนิดบางเครื่อง ความถี่สัญญาณนาฬิกาที่ต่างกันใช้สำหรับ PgCsLOS ที่ต่างกัน บางครั้งความถี่ของเครื่องกำเนิดหนึ่งขึ้นอยู่กับเอาต์พุตของอีกเครื่องหนึ่ง เหล่านี้เป็นรุ่นอิเล็กทรอนิกส์ทั้งหมดของแนวคิดเครื่องเข้ารหัสก่อนสงครามโลกครั้งที่สองที่เรียกว่าออสซิลเลเตอร์ที่ควบคุมด้วยนาฬิกา (นาฬิกา - เครื่องกำเนิดไฟฟ้าควบคุม ). การควบคุมนาฬิกาสามารถป้อนไปข้างหน้า โดยที่เอาต์พุตของ PgSsLOS ตัวหนึ่งจะควบคุมความเร็วสัญญาณนาฬิกาของ PgSsLOS อื่น หรือลูปปิด โดยที่เอาต์พุตของ PgSsLOS ตัวหนึ่งจะควบคุมนาฬิกาของตัวเอง แม้ว่าเครื่องกำเนิดสัญญาณเหล่านี้ทั้งหมดมีความละเอียดอ่อน อย่างน้อยในทางทฤษฎี ต่อการโจมตีแบบซ้อนและความสัมพันธ์ที่น่าจะเป็นไปได้ ส่วนใหญ่ยังคงปลอดภัย

Ian Cassells ซึ่งเคยดำรงตำแหน่งหัวหน้าฝ่ายคณิตศาสตร์ล้วนที่ Cambridge และนักเข้ารหัสที่ Bletchly Park กล่าวว่า "การเข้ารหัสเป็นส่วนผสมของคณิตศาสตร์และความสับสน และไม่มีความสับสน คณิตศาสตร์สามารถนำมาใช้กับคุณได้" สิ่งที่เขาหมายถึงคือในการเข้ารหัสสตรีม โครงสร้างทางคณิตศาสตร์บางอย่าง เช่น PrCcLOC จำเป็นสำหรับความยาวสูงสุดและคุณสมบัติอื่นๆ แต่ต้องมีการแนะนำความยุ่งเหยิงที่ไม่เป็นเชิงเส้นที่ซับซ้อนเพื่อป้องกันไม่ให้ผู้อื่นรับเนื้อหาของรีจิสเตอร์และการถอดรหัส อัลกอริทึม คำแนะนำนี้ใช้ได้กับอัลกอริธึมบล็อกด้วย

รหัสของสตรีมจริงส่วนใหญ่อิงจาก PrCsLOS แม้แต่ในยุคแรก ๆ ของอุปกรณ์อิเล็กทรอนิกส์ก็ยังสร้างได้ง่าย shift register เป็นเพียงอาร์เรย์ของบิต และลำดับการป้อนกลับคือชุดของเกท XOR แม้เมื่อใช้ VLSI การเข้ารหัสสตรีมที่ใช้ PrCsLOS ก็ให้การรักษาความปลอดภัยอย่างมากด้วยความช่วยเหลือของลอจิกเกตหลายตัว ปัญหาของ PgCsLOS คือการนำซอฟต์แวร์ไปใช้ไม่มีประสิทธิภาพมากนัก คุณต้องหลีกเลี่ยงพหุนามป้อนกลับแบบกระจัดกระจาย - มันทำให้การโจมตีแบบสหสัมพันธ์ง่ายขึ้น - และพหุนามป้อนกลับที่หนาแน่นนั้นไม่มีประสิทธิภาพ

การเข้ารหัสสาขานี้เติบโตอย่างรวดเร็วและอยู่ภายใต้การควบคุมของรัฐบาลที่ระมัดระวังจาก NSA . การพัฒนาส่วนใหญ่จัดอยู่ในประเภท - ระบบเข้ารหัสทางการทหารจำนวนมากที่ใช้อยู่ในปัจจุบันนั้นใช้ PrCsLOS อันที่จริง คอมพิวเตอร์ Cray ส่วนใหญ่ (Cray 1, Cray X-MP, Cray Y-MP) มีคำสั่งที่น่าสนใจมากโดยทั่วไปเรียกว่า "จำนวนประชากร" มันนับจำนวน 1 วินาทีในการลงทะเบียนและสามารถใช้ได้ทั้งสองอย่างเพื่อคำนวณระยะทางแฮมมิงระหว่างคำไบนารีสองคำอย่างมีประสิทธิภาพและเพื่อใช้ PrCcLOC เวอร์ชัน vectorized คำสั่งนี้ถือเป็นคำสั่งบัญญัติของ NSA และปรากฏในสัญญาทางคอมพิวเตอร์เกือบทั้งหมด

ในทางกลับกัน มีเครื่องกำเนิดสัญญาณ shift register ที่ซับซ้อนจำนวนมากอย่างน่าประหลาดใจที่ถูกแฮ็ก และแน่นอน จำนวนเครื่องกำเนิดไฟฟ้าที่ถูกแฮ็กโดยสถาบันการเข้ารหัสทางทหารเช่น NSA นั้นยิ่งใหญ่กว่า

1.3 ความซับซ้อนเชิงเส้นของลำดับที่สร้างขึ้นของตัวเลขสุ่มหลอก PrCsLOS

การเข้ารหัสสตรีมมักจะแยกวิเคราะห์ได้ง่ายกว่าบล็อกการเข้ารหัส ตัวอย่างเช่น พารามิเตอร์สำคัญที่ใช้ในการวิเคราะห์เครื่องกำเนิดไฟฟ้าที่ใช้ PgCsLOC คือความซับซ้อนเชิงเส้นหรือช่วงเชิงเส้น มันถูกกำหนดให้เป็นความยาว n ของ PrCsLOS ที่สั้นที่สุดที่สามารถจำลองเอาต์พุตของเครื่องกำเนิด ลำดับใดๆ ที่สร้างโดยหุ่นยนต์จำกัดขอบเขตบนเขตข้อมูลจำกัดจะมีความซับซ้อนเชิงเส้นจำกัด ความซับซ้อนเชิงเส้นมีความสำคัญเนื่องจากด้วยอัลกอริธึมอย่างง่ายที่เรียกว่าอัลกอริทึม Berlekamp-Massey เราสามารถกำหนด PrCcLOC นี้ได้โดยตรวจสอบคีย์สตรีมเพียง 2n บิต การสร้าง PrCsLOS ที่ต้องการขึ้นใหม่จะเป็นการทำลายรหัสของสตรีม

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

1.4 เกี่ยวกับความเป็นอิสระสหสัมพันธ์ของลำดับที่สร้างขึ้นของตัวเลขสุ่มหลอก PrCsLOS

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

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

การโจมตีแบบสหสัมพันธ์และรูปแบบต่างๆ เช่น การโจมตีแบบสหสัมพันธ์อย่างรวดเร็ว ถูกนำมาใช้อย่างประสบความสำเร็จกับเครื่องกำเนิดคีย์สตรีมแบบ PgCsLOC จำนวนมาก ซึ่งให้การแลกเปลี่ยนระหว่างความซับซ้อนและประสิทธิภาพในการคำนวณ

1.5 เกี่ยวกับวิธีการอื่นในการเปิดลำดับที่สร้างขึ้นของตัวเลขสุ่มหลอก PgCsLOS

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

2. คำอธิบายการใช้งานซอฟต์แวร์ของ PrCsLOS เป็นตัวสร้างลำดับสุ่มหลอก

2.1 รูปแบบทั่วไปของอัลกอริทึม

2.2 คำอธิบายของโมดูลซอฟต์แวร์และอินเทอร์เฟซ

รูปที่ 3 ด้านล่างแสดงหน้าต่างโปรแกรม

รูป โปรแกรมอินเตอร์เฟส

เมนูมีฟังก์ชันดังต่อไปนี้:

• ไฟล์ -> บันทึกรายงาน

ฟังก์ชันนี้สร้างไฟล์รายงาน โดยที่สถานะเริ่มต้นของ PrCsLOS ลำดับการแตะ ระยะเวลาของลำดับบิตสุ่มเทียมที่ได้รับ ลำดับนั้นเอง และตารางสถานะ หากบันทึกไฟล์สำเร็จ ข้อความเกี่ยวกับการบันทึกสำเร็จจะแสดงขึ้น (ภาพที่ 4) นามสกุลไฟล์ที่แนะนำสำหรับรายงานคือ *.txt

การวาดภาพ

• ไฟล์->ออก

ฟังก์ชันนี้ช่วยให้แน่ใจว่าแอปพลิเคชันปิดอยู่

• ตั้งค่าลำดับการหลบหนี

ฟังก์ชันนี้สร้างลำดับการแตะโดยการอ่านค่าจากเซลล์ที่ผู้ใช้ทำเครื่องหมายบนแบบฟอร์มหน้าจอ หลังจากนั้นจะแจ้งให้ผู้ใช้ทราบเกี่ยวกับการสร้างลำดับการแตะ (ภาพที่ 5) ลำดับการแตะจะกำหนดว่า flip-flop ของ shift register จะได้รับข้อเสนอแนะ XOR เพื่อสร้างบิตออฟเซ็ต ตามค่าเริ่มต้น ข้อเสนอแนะจากทริกเกอร์แรกจะเปิดอยู่เสมอ หากไม่มีการเชื่อมต่ออื่น การเลื่อนไปทางซ้ายจะดำเนินการโดยเปลี่ยนบิตที่มีนัยสำคัญน้อยที่สุดไปยังตำแหน่งของจุดที่สำคัญที่สุด

การวาดภาพ

• ตั้งค่าเริ่มต้น

ฟังก์ชันนี้อ่านค่าเริ่มต้นของการลงทะเบียนที่ผู้ใช้ป้อนจากหน้าต่างแก้ไข 1 และตรวจสอบค่าที่ป้อนตามเงื่อนไขที่กำหนด: สตริงที่ป้อนไม่ว่างเปล่า (รูปที่ 6) สตริงที่ป้อนมีความยาวแปด (8 บิต = 1 ไบต์ รูปที่ 7) สตริงที่ป้อนมีเพียงศูนย์และ / หรือ คน (รูปที่ 8) สตริงที่ป้อนไม่เป็นศูนย์ (รูปที่ 9) มิฉะนั้น ข้อความแสดงข้อผิดพลาดจะปรากฏขึ้น ผู้ใช้ต้องแก้ไขและกดปุ่มอีกครั้ง ในกรณีที่ตรวจสอบสำเร็จ ค่าเริ่มต้นจะถูกเขียนลงในตารางสถานะในบรรทัด "เริ่มต้น" และจะออกการแจ้งเตือน (รูปที่ 10)

การวาดภาพ

การวาดภาพ

การวาดภาพ

การวาดภาพ

การวาดภาพ

• ทำกะทะเบียน

ฟังก์ชันนี้จำลองการทำงานของ shift register การทำ 256 กะตามลำดับ แต่ละกะจะสร้างบิตเอาต์พุตของลำดับสุ่มหลอกและสถานะใหม่ของรีจิสเตอร์ ทันทีที่สถานะการลงทะเบียนเท่ากับค่าตั้งต้น ระยะเวลาจะถูกคำนวณและแสดงในฟิลด์บันทึก 1 ได้รับลำดับสุ่มหลอก

• ช่วยเหลือ -> เกี่ยวกับ

ฟังก์ชันนี้แสดงคำอธิบายสั้นๆ ของโปรแกรมและคำแนะนำ (ภาพที่ 11)

การวาดภาพ

• ช่วยเหลือ -> เกี่ยวกับผู้แต่ง

ฟังก์ชันนี้แสดงข้อมูลเกี่ยวกับผู้เขียนโปรแกรม (ภาพที่ 12)

การวาดภาพ

2.3 คู่มือผู้ใช้

1. ขั้นแรกให้ตั้งค่าสถานะเริ่มต้นของการลงทะเบียน ต้องมีแปดตัวไบนารี มิฉะนั้น ข้อความแสดงข้อผิดพลาดจะปรากฏขึ้น และคุณจะต้องแก้ไขค่าที่ป้อน กดรายการเมนู "ตั้งค่าเริ่มต้น"
2. จากนั้นทำเครื่องหมายที่ช่องทำเครื่องหมายเพื่อลงทะเบียนการตอบกลับ (แตะลำดับ) กดรายการเมนู "Set Tap Sequence"
3. จากนั้นคลิกรายการเมนู "ลงทะเบียนกะ" ตรวจสอบให้แน่ใจว่าคุณได้ทำขั้นตอนที่ 1 และ 2 เสร็จสมบูรณ์ก่อนที่จะดำเนินการนี้ มิฉะนั้น จะเกิดข้อผิดพลาดของซอฟต์แวร์
4. เมื่อได้รับผลลัพธ์แล้ว คุณสามารถบันทึกได้โดยคลิกที่รายการเมนู "ไฟล์->บันทึกรายงาน" ตรวจสอบให้แน่ใจว่าคุณได้ดำเนินการตามขั้นตอนที่ 1-3 เรียบร้อยแล้ว มิฉะนั้นจะเกิดข้อผิดพลาดของซอฟต์แวร์
5. หากต้องการความช่วยเหลือ ให้คลิกรายการเมนู "ไฟล์->เกี่ยวกับ", "ไฟล์->เกี่ยวกับผู้เขียน"
6. หากต้องการดูการทำงานของรีจิสเตอร์ด้วยค่าอื่นๆ ของลำดับการแตะและสถานะเริ่มต้นของรีจิสเตอร์ ให้ทำซ้ำขั้นตอนในขั้นตอนที่ 1-3 ตามลำดับ โดยป้อนพารามิเตอร์อื่นๆ

บทสรุป

ในบทความนี้ RgCsLOS ถือเป็นตัวสร้างตัวเลขสุ่มหลอก โปรแกรมสามารถใช้เป็นภาพสาธิตหลักการทำงานของรีจิสเตอร์กะพร้อมคำติชมเชิงเส้นบน XOR . คุณสามารถศึกษาหลักการสร้างลำดับบิตสุ่มหลอก ความสัมพันธ์ระหว่างค่าเริ่มต้นของรีจิสเตอร์และค่าของลำดับสุ่มหลอก ลำดับการแตะ และระยะเวลา แกมมาสุ่มเทียมที่เป็นผลลัพธ์สามารถใช้ในซอฟต์แวร์แอปพลิเคชันอื่นได้ (เช่น การใช้งานซอฟต์แวร์ของรหัสแกมมา)

ในปัจจุบัน การลงทะเบียนเหล่านี้ไม่ได้ถูกใช้เป็นเครื่องมือสร้างตัวเลขสุ่มหลอกแบบอิสระ แต่เป็นส่วนหนึ่งของอุปกรณ์ที่ซับซ้อนกว่า อย่างไรก็ตาม พวกเขาเป็นผู้เปิดทิศทางใหม่ในวิชาคณิตศาสตร์ (ค้นหาพหุนามดั้งเดิมในเขตข้อมูลจำกัด วิธีการทางคณิตศาสตร์สำหรับการทำลายตัวสร้างตัวเลขสุ่มหลอก) หากปราศจากความรู้เกี่ยวกับหลักการทำงานของเครื่องกำเนิดไฟฟ้าบน RgCsLOS จะไม่สามารถเข้าใจการทำงานของอุปกรณ์ที่ซับซ้อนกว่านี้ได้ เนื่องจากมีการใช้ฮาร์ดแวร์อย่างง่าย จึงมีการใช้กันอย่างแพร่หลายในด้านเทคโนโลยี การวิจัยของ PgCsOS ทำให้เกิดการเข้ารหัสใหม่ - บล็อกและสตรีม - ตามประเภทของการลงทะเบียนเหล่านี้ (รหัสการเปลี่ยนลำดับแบบเลื่อน DES ฯลฯ ; EDS, ฟังก์ชันแฮช)

โดยทั่วไป การวิจัยในพื้นที่นี้ได้กระตุ้นการพัฒนาวิทยาการเข้ารหัสลับและการเข้ารหัสลับ คอมพิวเตอร์และอุปกรณ์อย่างจริงจัง และยังทำให้สามารถใช้ฟังก์ชันที่มีประโยชน์อื่นๆ จำนวนหนึ่งได้ (เช่น การแก้ไขรหัสวงจร)

บรรณานุกรม

1. ชไนเออร์ บรูซ. การเข้ารหัสประยุกต์ โปรโตคอล อัลกอริธึม ข้อความต้นฉบับในภาษาซี - M.: Triumph, 2002
2. บาบาช เอ.วี. แง่มุมการเข้ารหัสและทฤษฎีอัตโนมัติของการรักษาความปลอดภัยข้อมูลที่ทันสมัย เล่มที่ 1 - ม.: ศ. ศูนย์ EAOI, 2552. - 414 น.
3. อี.เอส. เซลเมอร์ เอกสาร: "การเรียกซ้ำเชิงเส้นในฟิลด์จำกัด". มหาวิทยาลัยเบอร์เกน นอร์เวย์ ค.ศ. 1966
4. N. Zierler และ J. Brillhart "On Primitive Trinomials Modulo 2", Journal of Information and Control, Vol. 13 No. 6 December 1968, pp. 541-544.
5. เค.เค. เมเยอร์และดับเบิลยู แอล ทูคมัน "รหัสสุ่มหลอกสามารถถอดรหัสได้" นิตยสาร Electronic Design ฉบับที่ 23 พฤศจิกายน 2515
6. เจ.แอล.แมสซีย์ "ลักษณะทั่วไปของการลงทะเบียนกะและการถอดรหัสรหัส Bose-Chowdhury-Hokvingham",ธุรกรรม IEEE เกี่ยวกับทฤษฎีสารสนเทศ, v. IT-15, น . 1 มกราคม 2512 หน้า 122-127
7. เอส.ยู. โกลอมบ์ Shift Register Sequences, ซานฟรานซิสโก, Golden Day, 1967 (พิมพ์ซ้ำโดย Aigean Park Press, 1982)

ภาคผนวก A

ตารางพหุนามดั้งเดิมบางตัว โมดูโล 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

อินพุตสถานะเริ่มต้น (IS)

การตรวจสอบอินพุต

ออกข้อความแสดงข้อผิดพลาด

การตั้งค่าลำดับการแตะ

กำลังบันทึก IP ในตารางสถานะ

บันทึกฉัน - การลงทะเบียนสถานะและบิตเอาต์พุตในตารางสถานะ

IS==สถานะปัจจุบัน

บันทึกผล

เอาต์พุตลำดับสุ่มหลอก

ทางออก

ปล่อย

ใช่

ใช่

ไม่

ใน shift register พร้อมการป้อนกลับเชิงเส้น มีสองส่วน (โมดูล) ที่แตกต่างกัน: shift register เองและวงจร (หรือรูทีนย่อย) ที่คำนวณค่าของบิตที่แทรก รีจิสเตอร์ประกอบด้วยเซลล์ฟังก์ชัน (หรือบิตของคำเครื่องหรือหลายคำ) ซึ่งแต่ละเซลล์เก็บสถานะปัจจุบันไว้หนึ่งบิต จำนวนเซลล์เรียกว่าความยาวของรีจิสเตอร์ บิต (เซลล์) มักจะกำหนดหมายเลขด้วยตัวเลข ซึ่งแต่ละอันสามารถจัดเก็บบิตได้ และบิตที่คำนวณได้จะถูกผลักเข้าไปในเซลล์ และบิตที่สร้างต่อไปจะถูกดึงออกจากเซลล์ การคำนวณบิตที่แทรกมักจะดำเนินการก่อนการเปลี่ยนแปลงของรีจิสเตอร์และหลังจากกะคือค่าของบิตที่คำนวณแล้วที่วางอยู่ในเซลล์

ระยะเวลาของ shift register คือความยาวขั้นต่ำของลำดับผลลัพธ์ก่อนที่จะเริ่มทำซ้ำ เนื่องจากรีจิสเตอร์ของบิตเซลล์มีสถานะที่ไม่ใช่ศูนย์ที่แตกต่างกันเท่านั้น ดังนั้น โดยหลักการแล้ว ระยะเวลาของรีจิสเตอร์ต้องไม่เกินจำนวนนี้ หากระยะเวลาของการลงทะเบียนเท่ากับจำนวนนี้การลงทะเบียนดังกล่าวจะเรียกว่าการลงทะเบียนของระยะเวลาสูงสุด

สำหรับ LFSR ฟังก์ชันป้อนกลับเป็นฟังก์ชันบูลีนเชิงเส้นของสถานะของรีจิสเตอร์ทั้งหมดหรือบางส่วน ตัวอย่างเช่น ผลรวมโมดูโลสองหรือค่าผกผันเชิงตรรกะของมันคือฟังก์ชันบูลีนเชิงเส้น (การดำเนินการ XOR แสดงเป็นสูตร) ​​และมักใช้ในรีจิสเตอร์ดังกล่าว

ในกรณีนี้ บิตเหล่านั้นที่เป็นตัวแปรของฟังก์ชันป้อนกลับมักจะเรียกว่า โค้ง.

การลงทะเบียนการควบคุมในการใช้งานฮาร์ดแวร์ทำได้โดยใช้ชีพจรกะ (หรือเรียกว่า นาฬิกาหรือ ซิงค์ชีพจร) ไปยังเซลล์ทั้งหมดในซอฟต์แวร์ - โดยดำเนินการรอบโปรแกรม รวมถึงการคำนวณฟังก์ชันป้อนกลับและการเลื่อนบิตในคำ

ระหว่างขีดนาฬิกาแต่ละครั้ง การดำเนินการต่อไปนี้จะดำเนินการ:

การลงทะเบียนเปลี่ยนคำติชมเชิงเส้น

ดังนั้น การดำเนินการเชิงตรรกะ XOR (exclusive OR) จึงถือเป็นฟังก์ชันป้อนกลับ นั่นคือ:

คุณสมบัติของพหุนามดั้งเดิม

คุณสมบัติ

คุณสมบัติของลำดับที่สร้างโดย LFSR นั้นสัมพันธ์อย่างใกล้ชิดกับคุณสมบัติของพหุนามที่เกี่ยวข้อง สัมประสิทธิ์ที่ไม่ใช่ศูนย์เรียกว่า โค้งเช่นเดียวกับเซลล์ที่เกี่ยวข้องของรีจิสเตอร์โดยให้ค่าของอาร์กิวเมนต์ของฟังก์ชันป้อนกลับ

ความซับซ้อนเชิงเส้น

ความซับซ้อนเชิงเส้นของลำดับไบนารีเป็นหนึ่งในคุณลักษณะที่สำคัญที่สุดของการดำเนินการ LFSR ให้เราแนะนำสัญกรณ์ต่อไปนี้:

คำนิยาม

ความซับซ้อนเชิงเส้นของลำดับไบนารีอนันต์เรียกว่า ตัวเลข ซึ่งกำหนดไว้ดังนี้

ความซับซ้อนเชิงเส้นของลำดับเลขฐานสองจำกัดเรียกว่า ตัวเลข ซึ่งเท่ากับความยาวของ LFSR ที่สั้นที่สุด ซึ่งสร้างลำดับที่มีเป็นพจน์แรก

คุณสมบัติความซับซ้อนเชิงเส้น

อนุญาต และเป็นลำดับไบนารี แล้ว:

ความเป็นอิสระสหสัมพันธ์

เพื่อให้ได้ความซับซ้อนเชิงเส้นสูง นักเข้ารหัสพยายามรวมผลลัพธ์ของลำดับเอาต์พุตหลายรายการแบบไม่เชิงเส้น ในกรณีนี้ อันตรายคือลำดับเอาต์พุตตั้งแต่หนึ่งรายการขึ้นไป (มักจะเป็นเอาต์พุตของ LFSR แต่ละรายการด้วย) สามารถเชื่อมต่อด้วยสตรีมคีย์ทั่วไปและเปิดโดยใช้พีชคณิตเชิงเส้น การแฮ็กจากจุดอ่อนดังกล่าวเรียกว่า การชันสูตรพลิกศพ. Thomas Siegenthaler ได้แสดงให้เห็นว่าสามารถกำหนดความเป็นอิสระของสหสัมพันธ์ได้อย่างแม่นยำ และมีข้อแลกเปลี่ยนระหว่างความเป็นอิสระของสหสัมพันธ์และความซับซ้อนเชิงเส้น

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

การโจมตีแบบสหสัมพันธ์หรือรูปแบบต่างๆ เช่น การโจมตีแบบสหสัมพันธ์อย่างรวดเร็ว ประสบความสำเร็จในการใช้กับเครื่องกำเนิดคีย์สตรีมที่ใช้การป้อนกลับแบบเชิงเส้นจำนวนมาก ซึ่งเกี่ยวข้องกับการแลกเปลี่ยนระหว่างความซับซ้อนในการคำนวณและประสิทธิภาพ

ตัวอย่าง

สำหรับ LFSR ที่มีพหุนามที่เกี่ยวข้อง ลำดับที่สร้างขึ้นจะมีรูปแบบ . สมมติว่า ก่อนเริ่มกระบวนการ ลำดับถูกเขียนในรีจิสเตอร์ จากนั้นช่วงเวลาของบิตสตรีมที่สร้างขึ้นจะเท่ากับ 7 โดยมีลำดับต่อไปนี้:

หมายเลขขั้นตอน	สถานะ	สร้างบิต
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

เนื่องจากสถานะภายในในขั้นตอนที่เจ็ดจะกลับสู่สถานะเดิม จากนั้นจึงจะมีการทำซ้ำตั้งแต่ขั้นตอนถัดไป กล่าวอีกนัยหนึ่ง ช่วงเวลาของลำดับนั้นเท่ากับ 7 ซึ่งเกิดขึ้นเนื่องจากความดั้งเดิมของพหุนาม

อัลกอริทึมสำหรับการสร้างพหุนามดั้งเดิม

โต๊ะพร้อม

การคำนวณความดึกดำบรรพ์ของพหุนามเป็นปัญหาทางคณิตศาสตร์ที่ค่อนข้างซับซ้อน ดังนั้นจึงมีตารางสำเร็จรูปที่แสดงรายการหมายเลขของลำดับการแตะที่ให้ระยะเวลาสูงสุดของเครื่องกำเนิด ตัวอย่างเช่น สำหรับ shift register 32 บิต จะมีลำดับ ซึ่งหมายความว่าในการสร้างบิตใหม่ จำเป็นต้องรวมบิตที่ 31, 30, 29, 27, 25 และ 0 โดยใช้ฟังก์ชัน XOR รหัสสำหรับ LFSR ดังกล่าวในภาษา C มีดังนี้:

Int LFSR (เป็นโมฆะ ) ( คงที่ unsigned long S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ ส ) & 1 )<< 31 ) | (S>> 1); ส่งคืน S & 1 ; )

การใช้งานซอฟต์แวร์ของตัวสร้าง RSLOS นั้นค่อนข้างช้าและทำงานได้เร็วกว่าหากเขียนด้วยแอสเซมเบลอร์มากกว่าในภาษาซี ทางออกหนึ่งคือการใช้ 16 RLLS แบบขนาน (หรือ 32 ขึ้นอยู่กับความยาวของคำในสถาปัตยกรรมของคอมพิวเตอร์เครื่องใดเครื่องหนึ่ง) ในรูปแบบดังกล่าวจะใช้อาร์เรย์ของคำซึ่งมีขนาดเท่ากับความยาวของ LFSR และแต่ละบิตของคำอาร์เรย์หมายถึง LFSR หากใช้หมายเลขลำดับการแตะแบบเดียวกัน อาจให้ประสิทธิภาพที่เพิ่มขึ้นอย่างเห็นได้ชัด [ต้องการโค้ดตัวอย่าง] (ดู: bitslice).

การกำหนดค่า Galois

การกำหนดค่า Galois ของการลงทะเบียนกะผลป้อนกลับเชิงเส้น

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

Int LFSR (เป็นโมฆะ) ( static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

ข้อดีคือ XOR ทั้งหมดดำเนินการในการดำเนินการเดียว

• สามารถพิสูจน์ได้ว่าการกำหนดค่า Fibonacci ที่ให้มาก่อนและการกำหนดค่า Galois ที่ให้ไว้ที่นี่ให้ลำดับเดียวกัน (ความยาว 2 32 −1) แต่เปลี่ยนเฟสจากที่อื่น
• การวนซ้ำของจำนวนการเรียกใช้ฟังก์ชัน LFSR ในการกำหนดค่า Galois นั้นเร็วเป็นสองเท่าของการกำหนดค่า Fibonacci (คอมไพเลอร์ MS VS 2010 บน Intel Core i5)
• โปรดทราบว่าในการกำหนดค่า Galois ลำดับของบิตในคำป้อนกลับจะกลับกันเมื่อเทียบกับการกำหนดค่า Fibonacci

ตัวอย่างเครื่องกำเนิดไฟฟ้า

เครื่องกำเนิดไฟฟ้าแบบหยุดนิ่ง

เครื่องกำเนิดไฟฟ้าสลับหยุดและไป

ออสซิลเลเตอร์นี้ใช้เอาต์พุตของ LFSR หนึ่งเพื่อควบคุมความถี่สัญญาณนาฬิกาของ LFSR อื่น เอาต์พุตนาฬิกาของ RSLOS-2 ถูกควบคุมโดยเอาต์พุตของ RSLOS-1 เพื่อให้ RSLOS-2 สามารถเปลี่ยนสถานะได้ ณ เวลา t ต่อเมื่อเอาต์พุตของ RSLOS-1 ในเวลา t-1 เท่ากับหนึ่งเท่านั้น แต่โครงการนี้ไม่ได้ต่อต้านการเปิดความสัมพันธ์

ดังนั้นจึงมีการเสนอตัวสร้างที่ได้รับการปรับปรุงตามแนวคิดเดียวกัน มันถูกเรียกว่าเครื่องกำเนิดอินเตอร์ลีฟแบบหยุดและไป ใช้ LFSR สามตัวที่มีความยาวต่างกัน LFSR-2 ถูกโอเวอร์คล็อกเมื่อเอาต์พุตของ LFSR-1 เท่ากับหนึ่ง และ LFSR-3 เมื่อเอาต์พุตของ LFSR-1 เท่ากับศูนย์ เอาต์พุตของเครื่องกำเนิดไฟฟ้าคือผลรวมของโมดูโล 2 ของ RSLOS-2 และ RSLOS-3 เครื่องกำเนิดไฟฟ้านี้มีช่วงเวลาขนาดใหญ่และมีความซับซ้อนเชิงเส้นสูง ผู้เขียนยังได้แสดงวิธีการเปิดความสัมพันธ์ของ RLOS-1 แต่สิ่งนี้ไม่ได้ทำให้ตัวกำเนิดอ่อนแอลงอย่างมาก

Gollmann Cascade

Gollmann Cascade

Gollmann Cascade เป็นเวอร์ชันปรับปรุงของตัวสร้างการหยุดรถ ประกอบด้วยลำดับของ LFSR ซึ่งกำหนดเวลาของแต่ละรายการควบคุมโดย LFSR ก่อนหน้า หากเอาต์พุตของ LFSR-1 ณ เวลา t คือ 1 แสดงว่า LFSR-2 ถูกโอเวอร์คล็อก หากเอาต์พุตของ LFSR-2 ที่เวลา t คือ 1 แสดงว่า LFSR-3 ถูกโอเวอร์คล็อก เป็นต้น เอาต์พุตของ LFSR ล่าสุดคือเอาต์พุตของเครื่องกำเนิดไฟฟ้า หากความยาวของ LFSR เท่ากันและเท่ากับ n แสดงว่าความซับซ้อนเชิงเส้นของระบบ k LFSR คือ

แนวคิดนี้เรียบง่ายและสามารถใช้เพื่อสร้างลำดับที่มีช่วงเวลาขนาดใหญ่ ความซับซ้อนเชิงเส้นขนาดใหญ่ และคุณสมบัติทางสถิติที่ดี แต่น่าเสียดายที่พวกมันไวต่อการเปิดที่เรียกว่า "ล็อค" (ล็อคอิน) เพื่อความเสถียรที่มากขึ้น ขอแนะนำให้ใช้ k อย่างน้อย 15 นอกจากนี้ ควรใช้ LFSR แบบสั้นมากกว่า LFSR ที่มีความยาวน้อยกว่า

เครื่องกำเนิดธรณีประตู

เครื่องกำเนิดธรณีประตู

เครื่องกำเนิดไฟฟ้านี้พยายามที่จะหลีกเลี่ยงปัญหาด้านความปลอดภัยของเครื่องกำเนิดไฟฟ้าก่อนหน้าโดยใช้จำนวนตัวแปรของการลงทะเบียนกะ ในทางทฤษฎี เมื่อใช้ shift register จำนวนมากขึ้น ความซับซ้อนของ cipher จะเพิ่มขึ้น ซึ่งเกิดขึ้นในเครื่องกำเนิดนี้

เครื่องกำเนิดไฟฟ้านี้ประกอบด้วยรีจิสเตอร์การเปลี่ยนแปลงจำนวนมาก ซึ่งเอาต์พุตจะถูกป้อนไปยังฟังก์ชันการทำให้เป็นส่วนใหญ่ หากจำนวนหน่วยที่เอาต์พุตของรีจิสเตอร์มากกว่าครึ่งหนึ่งเครื่องกำเนิดจะสร้างหน่วย หากจำนวนศูนย์บนเอาต์พุตมากกว่าครึ่งหนึ่ง เครื่องกำเนิดจะสร้างศูนย์ เพื่อให้สามารถเปรียบเทียบจำนวนศูนย์และจำนวนศูนย์ได้ จำนวนการลงทะเบียนกะต้องเป็นเลขคี่ ความยาวของรีจิสเตอร์ทั้งหมดต้องเป็น coprime และพหุนามป้อนกลับต้องเป็นแบบพื้นฐาน เพื่อให้ระยะเวลาของลำดับที่สร้างขึ้นมีค่าสูงสุด

สำหรับกรณีของการลงทะเบียนกะสามกะ เครื่องกำเนิดสามารถแสดงเป็น:

ตัวสร้างนี้คล้ายกับตัวสร้าง Geff ยกเว้นว่าตัวสร้างธรณีประตูมีความซับซ้อนเชิงเส้นมากกว่า ความซับซ้อนเชิงเส้นของมันคือ:

โดยที่ , , คือความยาวของรีจิสเตอร์กะที่หนึ่ง ที่สอง และสาม

ข้อเสียของมันคือแต่ละบิตเอาต์พุตให้ข้อมูลบางอย่างเกี่ยวกับสถานะของ shift register เป็น 0.189 บิตที่แน่นอน ดังนั้นเครื่องกำเนิดไฟฟ้านี้จึงไม่สามารถต้านทานการเปิดความสัมพันธ์ได้

ประเภทอื่นๆ

ผอมบางตัวเอง

เครื่องกำเนิดไฟฟ้าที่ลดขนาดตัวเองเรียกว่าเครื่องกำเนิดไฟฟ้าที่ควบคุมความถี่ของตนเอง มีการเสนอเครื่องกำเนิดไฟฟ้าดังกล่าวสองประเภท อันแรกประกอบด้วยรีจิสเตอร์ป้อนกลับเชิงเส้นและวงจรบางวงจรที่โอเวอร์คล็อกรีจิสเตอร์นี้ขึ้นอยู่กับค่าเอาต์พุตของรีจิสเตอร์กะ หากเอาต์พุต LFSR เท่ากับหนึ่ง รีจิสเตอร์จะถูกโอเวอร์คล็อก d ครั้ง หากเอาต์พุตเป็นศูนย์ รีจิสเตอร์จะถูกโอเวอร์คล็อก k ครั้ง อันที่สองมีการออกแบบเกือบจะเหมือนกัน แต่มีการปรับเปลี่ยนบ้าง: ในวงจรการตอกบัตรเมื่อตรวจสอบ 0 หรือ 1 จะไม่ได้รับสัญญาณเอาท์พุตเอง แต่ XOR ของบิตบางบิตของ shift register พร้อมการป้อนกลับเชิงเส้น น่าเสียดายที่เครื่องกำเนิดไฟฟ้าประเภทนี้ไม่ปลอดภัย

ออสซิลเลเตอร์หลายอัตราพร้อมผลิตภัณฑ์ภายใน

ตัวสร้างนี้ใช้รีจิสเตอร์สองกะพร้อมการตอบสนองเชิงเส้นที่มีความถี่สัญญาณนาฬิกาต่างกัน: LFSR-1 และ LFSR-2 ความถี่สัญญาณนาฬิกาของ RLOS-2 นั้นสูงกว่าความถี่ RLLS-1 d เท่า แต่ละบิตของรีจิสเตอร์เหล่านี้จะถูกรวมเข้ากับการดำเนินการ AND ผลลัพธ์ของการดำเนินการ AND จะเป็น XORed ลำดับเอาต์พุตนำมาจากบล็อก XOR นี้ อีกครั้ง เครื่องกำเนิดนี้ไม่สมบูรณ์แบบ (มันไม่รอดจากการเปิดความสม่ำเสมอเชิงเส้น ถ้า - ความยาวของ LFSR-1 - ความยาวของ LFSR-2 และ d คืออัตราส่วนของความถี่สัญญาณนาฬิกา แสดงว่าสถานะภายในของ เครื่องกำเนิดไฟฟ้าสามารถรับได้จากลำดับเอาต์พุตของความยาว ) แต่มีความซับซ้อนเชิงเส้นสูงและประสิทธิภาพทางสถิติที่ยอดเยี่ยม

ข้อเสนอแนะ shift registerประกอบด้วยสองส่วน: ทะเบียนกะและ ฟังก์ชั่นข้อเสนอแนะ.

รูปที่ 19. การลงทะเบียนกะผลตอบรับ

โดยทั่วไป shift register คือลำดับขององค์ประกอบบางอย่างของวงแหวนหรือฟิลด์ นิยมใช้ นิดหน่อยกะลงทะเบียน ความยาวของรีจิสเตอร์ดังกล่าวแสดงเป็นจำนวนบิต ทุกครั้งที่ดึงบิต บิตทั้งหมดในรีจิสเตอร์จะเลื่อนไปทางขวาหนึ่งตำแหน่ง บิตที่สำคัญที่สุดใหม่คำนวณเป็นฟังก์ชันของบิตอื่นๆ ทั้งหมดในรีจิสเตอร์ เอาต์พุตมักจะเป็นบิตที่มีนัยสำคัญน้อยที่สุด ระยะเวลาของ shift register คือความยาวของลำดับเอาต์พุตก่อนที่จะเริ่มทำซ้ำ

ประเภทที่ง่ายที่สุดของการลงทะเบียนกะคือการลงทะเบียนกะผลป้อนกลับเชิงเส้น (LFSR หรือ LRS) คำติชมเป็นการดำเนินการ XOR อย่างง่ายในบางบิตของรีจิสเตอร์ รายการของบิตเหล่านี้ถูกกำหนด พหุนามลักษณะเฉพาะและเรียก ลำดับการแตะ. บางครั้งโครงร่างนี้เรียกว่า การกำหนดค่าฟีโบนักชี.

รูปที่ 20 LFOS ของการกำหนดค่า Fibonacci

ในการใช้งานซอฟต์แวร์ของ LFSR จะใช้รูปแบบที่ปรับเปลี่ยน: เพื่อสร้างบิตที่สำคัญใหม่ แทนที่จะใช้บิตของลำดับการแตะ การดำเนินการ XOR จะดำเนินการในแต่ละบิตด้วยเอาต์พุตของเครื่องกำเนิดไฟฟ้า แทนที่บิตเก่า บิตของลำดับการแตะ การปรับเปลี่ยนนี้บางครั้งเรียกว่า การกำหนดค่า Galois.

รูปที่ 21 RLOS ของการกำหนดค่า Galois

น-bit LFSR สามารถเป็นหนึ่งใน2 น- 1 สภาพภายใน ซึ่งหมายความว่า ตามทฤษฎีแล้ว รีจิสเตอร์ดังกล่าวสามารถสร้างลำดับสุ่มหลอกด้วยคาบ 2 น– 1 บิต (การเติมด้วยศูนย์นั้นไร้ประโยชน์โดยสิ้นเชิง) ทางเดินของทั้งหมด2 น– 1 สถานะภายในเป็นไปได้เฉพาะกับลำดับการแตะบางอย่างเท่านั้น การลงทะเบียนดังกล่าวเรียกว่า LFSR โดยมีระยะเวลาสูงสุด เพื่อให้แน่ใจว่าระยะเวลาสูงสุดของ LFSR จำเป็นต้องมีพหุนามที่เป็นลักษณะเฉพาะ be ดั้งเดิมโมดูโล 2 ดีกรีของพหุนามคือความยาวของรีจิสเตอร์กะ พหุนามดีกรีดั้งเดิม น- มันเป็นเช่นนั้น ลดไม่ได้พหุนามที่เป็นตัวหารแต่ไม่ใช่ตัวหาร x d+1 สำหรับทุกคน dซึ่งเป็นตัวหารของ2 น– 1. (เมื่อพูดถึงพหุนาม คำว่า จำนวนเฉพาะแทนที่ด้วยคำว่า พหุนามลดไม่ได้). พหุนามลักษณะของ LFSR ที่แสดงในรูป:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

เป็นโมดูโลดั้งเดิม 2 ระยะเวลาของการลงทะเบียนดังกล่าวจะสูงสุด โดยวนผ่านค่า 2 32 - 1 ทั้งหมดจนกว่าจะทำซ้ำ ที่ใช้กันมากที่สุดคือพหุนามบาง ๆ เช่น ซึ่งมีค่าสัมประสิทธิ์เพียงบางส่วนเท่านั้น trinomials ที่นิยมมากที่สุด

พารามิเตอร์ที่สำคัญของเครื่องกำเนิดไฟฟ้าตาม LFSR คือ ความซับซ้อนเชิงเส้น. มันถูกกำหนดให้เป็นความยาว น LFSR ที่สั้นที่สุดที่สามารถจำลองเอาท์พุตของเครื่องกำเนิดไฟฟ้าได้ ความซับซ้อนเชิงเส้นมีความสำคัญเพราะด้วยความง่าย อัลกอริทึม Berlenkamp-Masseyเป็นไปได้ที่จะสร้าง LFSR ดังกล่าวใหม่โดยการตรวจสอบเพียง2 นแกมมาบิต ด้วยคำจำกัดความของ LFSR ที่ต้องการ รหัสสตรีมจะใช้งานไม่ได้จริง

ลำดับการลงทะเบียน Shift ใช้ในทฤษฎีการเข้ารหัสและการเข้ารหัส ทฤษฎีของพวกเขาได้รับการพัฒนามาอย่างดี การเข้ารหัสสตรีมแบบลงทะเบียนกะทำงานเป็นกลไกหลักในการเข้ารหัสทางการทหารมานานก่อนการถือกำเนิดของอุปกรณ์อิเล็กทรอนิกส์

การลงทะเบียนกะผลป้อนกลับประกอบด้วยสองส่วน: การลงทะเบียนกะและฟังก์ชันป้อนกลับ (รูปที่ 1.2.1) shift register เป็นลำดับของบิต (จำนวนบิตถูกกำหนดโดยความยาวของ shift register หากความยาวเป็น n บิต รีจิสเตอร์จะเรียกว่า n-bit shift register) เมื่อใดก็ตามที่จำเป็นต้องแยกบิต บิตทั้งหมดของ shift register จะเป็น เลื่อนไปทางขวา 1 ตำแหน่ง บิตซ้ายสุดใหม่เป็นฟังก์ชันของบิตอื่นๆ ทั้งหมดในรีจิสเตอร์ ผลลัพธ์ของ shift register เป็นหนึ่งบิตซึ่งมักจะมีความสำคัญน้อยที่สุด ระยะเวลาของ shift register คือความยาวของลำดับผลลัพธ์ก่อนที่จะเริ่มทำซ้ำ

ข้าว. 1.2.1.

นักเข้ารหัสชอบการเข้ารหัสสตรีมตาม shift register: ง่ายต่อการใช้งานกับฮาร์ดแวร์ดิจิทัล ฉันจะพูดถึงทฤษฎีทางคณิตศาสตร์สั้น ๆ เท่านั้น ในปีพ.ศ. 2508 เอิร์นส์ เซลเมอร์ หัวหน้าเจ้าหน้าที่เข้ารหัสลับของรัฐบาลนอร์เวย์ ได้พัฒนาทฤษฎีของลำดับการลงทะเบียนกะ Solomon Golomb นักคณิตศาสตร์ของ NSA เขียนหนังสือสรุปผลงานของเขาและ Selmer

ชนิดที่ง่ายที่สุดของการลงทะเบียนกะผลป้อนกลับคือการลงทะเบียนกะผลตอบรับเชิงเส้นหรือ LFSR (รูปที่ 1.2.2) คำติชมเป็นเพียง XOR ของบางบิตในรีจิสเตอร์ รายการของบิตเหล่านี้เรียกว่าลำดับการแตะ บางครั้งการลงทะเบียนดังกล่าวเรียกว่าการกำหนดค่าฟีโบนักชี เนื่องจากความเรียบง่ายของลำดับผลป้อนกลับ ทฤษฎีทางคณิตศาสตร์ที่ค่อนข้างสูงจึงสามารถใช้ในการวิเคราะห์ LFSR ได้ นักเข้ารหัสชอบที่จะวิเคราะห์ซีเควนซ์ โดยเชื่อว่าซีเควนซ์เหล่านี้เป็นแบบสุ่มมากพอที่จะปลอดภัย LFSR มักใช้ในการเข้ารหัสมากกว่า shift register อื่นๆ

ข้าว. 1.2.2.

ในรูป 1.2.3 แสดง LFSR 4 บิตโดยแตะบิตที่หนึ่งและสี่ หากเริ่มต้นด้วยค่า 1111 ก่อนที่จะทำซ้ำการลงทะเบียนจะใช้สถานะภายในต่อไปนี้:

ข้าว. 1.2.3. 4

ลำดับเอาต์พุตจะเป็นสตริงของบิตที่มีนัยสำคัญน้อยที่สุด:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

LFSR n-bit อาจอยู่ในสถานะภายใน 2n-1 อย่างใดอย่างหนึ่ง ซึ่งหมายความว่า ตามทฤษฎีแล้ว รีจิสเตอร์ดังกล่าวสามารถสร้างลำดับสุ่มหลอกด้วยช่วงเวลา 2n-1 บิต (จำนวนสถานะภายในและระยะเวลาคือ 2n-1 เนื่องจากการเติม LFSR ด้วยศูนย์จะทำให้ shift register แสดงลำดับของศูนย์ที่ไม่สิ้นสุด ซึ่งไร้ประโยชน์อย่างยิ่ง) เฉพาะกับลำดับการแตะบางลำดับเท่านั้น LFSR จะหมุนเวียน สถานะภายใน 2n-1 ทั้งหมด LFSR ดังกล่าวคือ LFSR ที่มีระยะเวลาสูงสุด ผลลัพธ์ที่ได้เรียกว่าลำดับ M

เพื่อให้ LFSR เฉพาะมีคาบสูงสุด พหุนามที่เกิดขึ้นจากลำดับการต๊าปและค่าคงที่ 1 ต้องเป็นโมดูโลดั้งเดิม 2 ดีกรีของพหุนามคือความยาวของรีจิสเตอร์กะ พหุนามดั้งเดิมของดีกรี n คือพหุนามลดทอนที่เป็นตัวหารแต่ไม่ใช่ตัวหารของ xd+1 สำหรับ d ทั้งหมดที่เป็นตัวหารของ 2n-1

โดยทั่วไป ไม่มีวิธีง่ายๆ ในการสร้างพหุนามดั้งเดิมของดีกรีโมดูโล 2 วิธีที่ง่ายที่สุดคือการเลือกพหุนามโดยการสุ่มและตรวจสอบว่าพหุนามพหุนามเป็นพหุนามหรือไม่ ไม่ใช่เรื่องง่าย และเหมือนกับการตรวจสอบเพื่อดูว่าตัวเลขที่เลือกแบบสุ่มเป็นจำนวนเฉพาะหรือไม่ แต่ชุดซอฟต์แวร์คณิตศาสตร์จำนวนมากสามารถทำได้

พหุนามบางพหุนามที่มีดีกรีต่างกันบางตัว แต่ไม่ใช่ทั้งหมดนั้นเป็นโมดูโลดั้งเดิม 2 ตัวอย่างเช่น สัญกรณ์ (32, 7, 5, 3, 2, 1, 0) หมายความว่าพหุนามต่อไปนี้เป็นโมดูโลดั้งเดิม 2:

x32 + x7 +x5 + x3 + x2 + x + 1

สิ่งนี้สามารถสรุปเป็น LFSR ได้อย่างง่ายดายด้วยระยะเวลาสูงสุด ตัวเลขแรกคือความยาวของ LFSR ตัวเลขสุดท้ายเป็น 0 เสมอและสามารถละเว้นได้ ตัวเลขทั้งหมดยกเว้น 0 ระบุลำดับการแตะ นับจากขอบด้านซ้ายของการลงทะเบียนกะ นั่นคือ เงื่อนไขของพหุนามที่มีดีกรีต่ำกว่าจะสัมพันธ์กับตำแหน่งที่ใกล้กับขอบด้านขวาของรีจิสเตอร์

ต่อจากตัวอย่าง การเขียน (32, 7, 5, 3, 2, 1, 0) หมายความว่าสำหรับการลงทะเบียนกะ 32 บิตที่กำหนด บิตใหม่จะถูกสร้างขึ้นโดย XORing สามสิบวินาที, เจ็ด, ห้า, สาม, วินาที และบิตแรกผลลัพธ์ LFSR จะมีความยาวสูงสุด โดยวนผ่านค่า 232-1 ก่อนทำซ้ำ