มีเครื่องมืออะไรบ้างในการทำวิศวกรรมย้อนกลับ LFSR นอกเหนือจาก BMA

ยังไม่ชัดเจนว่า "รหัสเวลาที่แน่นอน" คืออะไร แต่ฉันจะถือว่ามันหมายถึงลำดับความยาวจำกัด $s_0, s_1, \ldots, s_{N-1}$ ของ $N$ บิต ลำดับนั้นอาจถูกสร้างขึ้นโดย LFSR หรือไม่ เราไม่รู้ แต่เราต้องการหา LFSR (ฟีโบนัชชี) ที่สร้างลำดับ

มาตั้งเวทีกันสักหน่อย Fibonacci LFSR ของความยาว $n$ เป็นอาร์เรย์ของ $n$ บิตที่มีค่าเริ่มต้น $$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1})$$ และค่านิยมที่สืบต่อกันมา $$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\ \ลูกศรลง\ (s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\ \ลูกศรลง\ (s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\ \ลูกศรลง\ \cdots \quad \cdots$$ โดยที่เนื้อหาอาร์เรย์จะเลื่อนไปทางซ้ายในแต่ละขั้นตอน (รอบนาฬิกา) เพื่อให้บิตตกลง ออกจากปลายด้านซ้าย (LFSR เอาต์พุต) เป็นลำดับที่กำหนด ในขณะที่ บิตที่แสดงเป็น เข้าสู่ LFSR ทางด้านขวา เป็น กำลังคำนวณ เป็น การรวมกันเชิงเส้น (a.k.a. Exclusive-OR sum) ของ บาง ของ LFSR เนื้อหาในขั้นตอนที่แล้ว โดยเฉพาะอย่างยิ่งสำหรับ $i \geq 0$, เดอะ การเปลี่ยนสถานะ สามารถแสดงเป็น $$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\ \ลูกศรลง\ \biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad {\Large{\oplus}}_{j=0}^ {n-1}c_{n-j} s_{i+j}\biggr),$$ ที่ไหน $c_i$มีค่า $0$ หรือ $1$เพื่อให้การ เชิงเส้น การผสมผสาน $c_ns_i\oplus c_{n-1}s_{i+1} \oplus \cdots \oplus c_1s_{i+n-1}$ ของก่อนหน้านี้ กำลังมีเนื้อหา LFSR เลี้ยงกลับ เข้าทางด้านขวาสุดของ LFSR เช่น $s_{n+i}$ คือผลรวม Exclusive-OR ของเนื้อหาก่อนหน้านี้ไม่กี่บิตที่เลือกไว้ (เนื้อหาที่สอดคล้องกัน $c_i$ มีค่า $1$). ดังนั้นชื่อรีจิสเตอร์กะป้อนกลับเชิงเส้นซึ่งเริ่มต้นเป็น LFSR

ด้วยคำอธิบายข้างต้น คำตอบหนึ่งสำหรับคำถามของ LFSR นั้นไม่สำคัญในแง่หนึ่ง: $N$ เวที LFSR พร้อมค่าสัมประสิทธิ์ป้อนกลับ $(c_N,c_{N-1}, \cdots, c_1) = (1,0,0,\cdots, 0)$ และการโหลดครั้งแรก $\big(s_0, s_1, \ldots, s_{N-1}\big)$ จะผลิตซ้ำไม่รู้จบ $$s_0, s_1, \ldots, s_{N-1},s_0, s_1, \ldots, s_{N-1}, s_0, s_1, \ldots, s_{N-1}, \cdots$$ ของรหัสเวลาที่กำหนด $s_0, s_1, \ldots, s_{N-1}$ ตลอดกาลนาน อีกทางหนึ่ง ใดๆ ทางเลือกอื่นของ $(c_N,c_{N-1}, \cdots, c_1)$ จะเติม shift register ด้วยสิ่งอื่น แต่ก่อนอื่น $N$ บิตออกจะยังคงอยู่ $s_0, s_1, \ldots, s_{N-1}$ และสิ่งที่ตามมาหลังจากนั้นก็จะแตกต่างออกไป นี่ไม่ใช่สิ่งที่เราต้องการอย่างชัดเจน ดังนั้นเราจึงแสวงหาเกณฑ์ที่ดีกว่า: ค้นหา สั้นที่สุด LFSR (และการโหลดเริ่มต้น) ที่จะสร้างขึ้น $s_0, s_1, \ldots, s_{N-1}$และนั่นคือสิ่งที่ Berlekamp-Massey อัลกอริทึมค้นพบ

อัลกอริทึม Berlekamp-Massey เป็นกระบวนการวนซ้ำซึ่งประกอบด้วยการค้นหา LFSR ที่สั้นที่สุดที่สร้าง $t$ บิต $s_0, s_1, \ldots s_{t-1}$ และตรวจสอบว่า LFSR พบ $s_t$ อย่างถูกต้อง ถ้าใช่, $s_{t+1}$ มีการตรวจสอบ ในขณะที่ถ้าไม่ใช่ $c_i$มีการปรับปรุงเพื่อให้ ปรับปรุง LFSR สร้าง $s_t$. บ่อยครั้งที่ความยาวของ LFSR เพิ่มขึ้น แต่ไม่เสมอไป กระบวนการวนซ้ำจะดำเนินต่อไปจนถึงบิตสุดท้ายที่มีอยู่ $s_{N-1}$ ได้รับการประมวลผล ดังนั้นเมื่อ Berlekamp-Massey อัลกอริทึมยุติลง LFSR ที่สังเคราะห์ขึ้นจะสร้างลำดับทั้งหมด $s_0, s_1, \ldots, s_{N-1}$ ที่เอาต์พุต ถ้า LFSR ที่สังเคราะห์ได้ $n\leq N$ ขั้นตอนแล้วการโหลดเริ่มต้นคือ $\big(s_0, s_1, \ldots, s_{n-1}\big)$ (ซึ่งเป็นข้อแรก $n$ เอาต์พุตบิต) และ LFSR คำนวณได้อย่างถูกต้อง $s_n, s_{n+1}, \cdots, s_{N-1}$ (นั่นคือส่วนที่เหลือของลำดับที่กำหนด) รับประกันความยาวของ LFSR ที่สังเคราะห์โดย Berlekamp-Massey ขั้นต่ำ: ไม่ LFSR ที่สร้าง $s_0, s_1, \ldots, s_{N-1}$ สามารถมี สั้นลง ความยาว. อย่างไรก็ตาม, มี ไม่ อ้างว่า $n$ รับรองว่าเล็กกว่า $N$; อาจเป็นไปได้ว่าวิธีแก้ปัญหาเล็กน้อยที่อธิบายไว้ข้างต้นเป็นวิธีแก้ปัญหาขั้นต่ำ อันที่จริงฉันยืนยันว่านี่เป็นกรณีสำหรับ ที่สุด ลำดับ; LFSR มีความยาว $N$. ทฤษฎีความซับซ้อนของคอลโมโกรอฟ กล่าวว่าโปรแกรมที่สั้นที่สุดสำหรับการพิมพ์สตริงที่มีความยาวมากที่สุด $N$ มีความยาว $N+c$หรือเรียกขาน สำหรับสตริงส่วนใหญ่ เราสามารถทำได้ดีกว่าเพียงแค่เก็บสตริงและพิมพ์ออกมา "$ค$" เป็นเพียงความยาวของคำสั่ง "พิมพ์สตริงต่อไปนี้" ในบริบทของ shift registers สำหรับลำดับความยาวส่วนใหญ่ $N$, shift register ที่สั้นที่สุดซึ่งมีเอาต์พุตเป็นลำดับความยาวที่กำหนด $N$ เป็นเพียง shift register ของความยาว $N$ เริ่มต้นตามลำดับที่กำหนด ข้อเสนอแนะคืออะไร (หากมีข้อเสนอแนะใด ๆ เลย) นั้นไม่เกี่ยวข้อง

• หากลำดับถูกสร้างขึ้นโดย a $n$-stage LFSR ตามที่อธิบายไว้ข้างต้น โดยที่ $n \leq \frac N2$, จากนั้น Berlekamp-Massey อัลกอริทึมค้นหาทั้งหมด $n$ ค่าสัมประสิทธิ์ $c_i$ หลังจาก ตรวจสอบ $s_0, s_1, \ldots, s_{2n-1}$. แน่นอนว่าการโหลดเริ่มต้นของ LFSR ที่สังเคราะห์ขึ้นนั้นเป็นเพียง $\big(s_0, s_1, \ldots, s_{n-1}\big)$. จากนี้ ชี้เป็นต้นไป อัลกอริทึม Berlekamp-Massey สามารถ ตรวจสอบลำดับที่เหลือต่อไป (หากเป็นเช่นนั้น ต้องการ) แต่ไม่ต้องปรับปรุง $c_i$'s เนื่องจากการตรวจสอบสัญลักษณ์ถัดไปแต่ละครั้งจะรายงาน กลับมาว่าทุกอย่างเรียบร้อยดี LFSR ปัจจุบันสร้างบิตถัดไปด้วย อย่างไรก็ตามโดยทั่วไปแล้ว cryptanalyst มี ไม่ แนวคิดว่ารหัสเวลาถูกสร้างขึ้นโดย LFSR หรือไม่ มันเป็นเพียงลำดับของ $N$ บิตที่ไม่ทราบที่มา และเพื่อจุดประสงค์ของนักเข้ารหัสลับ ทั้งหมด $N$ ต้องตรวจสอบบิตเพื่อหา LFSR ที่สั้นที่สุดที่สามารถสร้างได้ $s_0, s_1, \ldots, s_{N-1}$. หากบิตเพิ่มเติม $s_N, s_{N+1}, \ldots$ มีอยู่ จึงไม่รับประกันว่าพบ LFSR หลังจากตรวจสอบแล้ว $N$ บิตจะสร้างบิตเพิ่มเติมเหล่านี้ด้วย ในความเป็นจริง แนวคิดทั้งหมดที่อยู่เบื้องหลังอัลกอริทึม Berlekamp-Massey คือหากการทดสอบ "LFSR ปัจจุบันสร้าง $s_n$ล้มเหลว อัลกอริทึมสังเคราะห์ LFSR ที่แก้ไขจาก LFSR ปัจจุบันเพื่อให้ LFSR ที่แก้ไขสร้าง $s_0, s_1, \ldots, s_{n-1},s_n$. ในกระบวนการนี้ ความยาว ของ LFSR อาจ (หรืออาจไม่) เพิ่มขึ้น
• หากลำดับถูกสร้างขึ้นโดย a $n$-stage LFSR ตามที่อธิบายไว้ข้างต้น โดยที่ $\frac N2 < n \leq N$, Berlekamp-Massey จะค้นหา LFSR ที่สั้นที่สุดที่สร้างขึ้น $s_0, s_1, \ldots, s_{N-1}$. อาจสร้างค่าเดียวกันหรือไม่ก็ได้ $s_N, s_{N+1}, \cdots, s_{2n-1}$ เช่นเดียวกับที่ LFSR ทำจริง

เมื่อคำนึงถึงคำวิจารณ์ที่มีความยาวข้างต้นแล้ว ให้เราตอบคำถามของ OP ในชื่อ OP ถาม

มีเครื่องมืออะไรบ้างในการทำวิศวกรรมย้อนกลับ LFSR นอกเหนือจาก BMA

ก็ อัลกอริทึมแบบยุคลิดแบบขยาย สำหรับตัวหารร่วมมากแบบโพลิโนเมียลก็สามารถใช้ได้ แต่ในแง่หนึ่ง มันก็เทียบเท่ากับอัลกอริทึมของแบร์เลแคมป์-แมสซีย์ สามารถดูได้ว่าเป็นการประมวลผลลำดับในลำดับย้อนกลับ $s_{N-1}, s_{N-2}, \cdots, s_1, s_0$ เมื่อเทียบกับการสั่งซื้อ $s_0, s_1, \cdots, s_{N-2}, s_{N-1}$ ใช้โดยอัลกอริทึมของ Berlekamp-Massey

ในเนื้อหาของคำถาม OP จะบ่น

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

น่าจะเป็นเรื่องของความผิดพลาดในการดำเนินการของกทม. "ไม่สามารถใช้งานได้ในทางใดทางหนึ่ง" แสดงให้เห็นว่าหน่วยความจำอาจไม่เพียงพอสำหรับการจัดเก็บพหุนามต่างๆ ที่ใช้ภายใน BMA หรือบัฟเฟอร์ล้น เป็นต้น ตามที่ @kodlu ชี้ให้เห็น หากรหัสเวลามีความยาว $220$ บิตแล้วตรวจสอบทั้งหมด $220$ บิตอาจส่งผลให้มีความยาว LFSR $110$. มิฉะนั้น ตามที่กล่าวไว้ข้างต้น หากรหัสเวลามีความยาว $110$ หรือมากกว่านั้น (อาจจะ $128$ บิต $= 16$ ไบต์?) BMA อาจสังเคราะห์ความยาว LFSR ได้ดี $110$. สุดท้าย ฉันไม่มีคำอธิบายอื่นใดนอกจากข้อผิดพลาดของโปรแกรมเมอร์สำหรับการสังเกตของ OP ว่าในเอาต์พุต LFSR ที่สังเคราะห์แล้ว "บิตแรก" นั้นถูกต้อง แต่ส่วนที่เหลือกลับด้าน

ใครมีเงื่อนงำภายใต้เงื่อนไขใดที่กทม.ตรวจพบพหุนามที่ยาวมากเช่นนี้?

ดูเนื้อหาที่อยู่เหนือเส้นประในคำตอบนี้