ทำความเข้าใจความไม่เชิงเส้นใน Salsa20 ในวงแหวนต่างๆ

ในการออกแบบ Salsa20 เบิร์นสไตน์เขียนเพื่อให้แน่ใจว่าไม่เป็นเชิงเส้นตรงที่เขาเลือก

การเพิ่ม 32 บิต (ทำลายความเป็นเส้นตรง $Z/2$), xor แบบ 32 บิต (ทำลายความเป็นเชิงเส้นมากกว่า $Z/2^32) และการหมุนแบบ 32 บิตแบบระยะทางคงที่ (การกระจายการเปลี่ยนแปลงจากบิตสูงเป็นบิตต่ำ)

คุณช่วยฉันเข้าใจเรื่องนี้ได้ไหม ฟังก์ชันเชิงเส้นเป็นหนึ่งในนั้น $f(ax+by) = af(x) + bf(y)$. ดูเหมือนว่าการบวกและ xor จะเป็นเชิงเส้นหรือไม่นั้นขึ้นอยู่กับนิยามของการบวกและการคูณที่คุณใช้ ซึ่งขึ้นอยู่กับวงแหวนที่คุณใช้ แต่การหมุนจะเป็นเชิงเส้นในวงแหวนใดๆ

อีกด้วย, $f$ รับหนึ่งอินพุต ในขณะที่ 32 บิตบวกหรือ xor รับสองอินพุต ซึ่งแต่ละอินพุตเป็นส่วนหนึ่งขององค์ประกอบ 512 บิต ฉันถือว่าฟังก์ชัน 2-ary เป็นเชิงเส้น ถ้าการแก้ไขอินพุตแรกทำให้เป็นฟังก์ชันเชิงเส้น 1-ary

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

ค่อนข้างถูกต้อง การดำเนินการที่เป็นเชิงเส้นในวงแหวนหนึ่งไม่จำเป็นต้องเป็นเชิงเส้นในวงแหวนอื่น

แต่การหมุนเป็นเส้นตรงในวงแหวนใดๆ

ไม่; การหมุนไม่เป็นเส้นตรงในวงแหวน $\mathbb{Z}/{2^{32}}$

นี่คือตัวอย่าง: $F(x)$ เป็น $x$ หมุนไปทางขวาหนึ่งตำแหน่ง

แล้ว, $F(1+1) = F(2) = 1$, อย่างไรก็ตาม $F(1) + F(1) = 2^{31} + 2^{31} = 0$, เพราะฉะนั้น $F$ ไม่เป็นเชิงเส้น

ฉันถือว่าฟังก์ชัน 2-ary เป็นเชิงเส้น ถ้าการแก้ไขอินพุตแรกทำให้เป็นฟังก์ชันเชิงเส้น 1-ary

ไม่; หากเป็นเช่นนั้น การคูณจะเป็นการดำเนินการเชิงเส้น (เพราะถ้าคุณกำหนดอินพุตตัวใดตัวหนึ่ง