無密鑰密碼證明
我昨天在 StackOverflow 上回答了一個問題，詢問為什麼以下 16 位數字的無密鑰編碼/解碼方案有效：
編碼
- 請注意，“移位”操作是旋轉移位，而不僅僅是算術移位。
- 另請注意，我正在使用 $ \oplus $ 表示按位 $ XOR $ 手術。
$$ L(m) = m \oplus (m<<6)\oplus(m<<10) $$
解碼
$$ m = L \oplus ( L<<2 ) \oplus ( L<<4 ) \oplus ( L<<12 ) \oplus ( L<<14 ) $$
我解決問題的方法是通過蠻力擴展 $ (L<<n) $ 按照 $ m $ 並註意到所有因素如何抵消離開 $ m = m $ 最後（您可以在我的 Stack Overflow 答案中看到所有步驟）。
但是，我無法找到它的數學證明，因為我無法推廣 XOR 和旋轉操作。你可以幫幫我嗎？我認為證明可能涉及伽羅瓦場以及我們如何定義 XOR 和旋轉 $ {0,1}^p $ 設置，但在這種直覺之後我一無所知。
如果我們辨識 16 位字 $ m=m_{15}\ldots m_0 $ 與 $ GF(2) $ 多項式 $ m(X):=m_{15}X^{15}\oplus\cdots m_1X\oplus m_0 $ , 然後異或字對應於多項式的加法和旋轉 $ k $ 位置對應於乘以 $ X^k $ 和減少模式 $ X^{16}\oplus 1 $ .
因此，在多項式土地中，操作 $ L(m) $ 對應於乘法 $ m(X) $ 由多項式 $ 1\oplus X^6\oplus X^{10} $ 和減少模式 $ X^{16}\oplus 1 $ . 為了反轉操作，我們需要一個多項式 $ R(X) $ 這樣 $$ R(X)(1\oplus X^6\oplus X^{10})\equiv 1\pmod{X^{16}\oplus 1}. $$
您可以使用二進制多項式的擴展歐幾里得算法或使用以下 sagemath 程式碼找到它：
PR.<X>=PolynomialRing(GF(2)) QR.<z>=QuotientRing(PR,ideal(X^16+1)) 1/(1+z^6+z^10)它告訴你 $ R(X)=X^{14}\oplus X^{12}\oplus X^4\oplus X^2\oplus 1 $ . 然後，您可以將其轉換回移位符號以獲取解碼過程。
請注意，如果試圖概括這一點，如果被乘數與 $ X^{16}\oplus 1 $ 在這種情況下，不存在乘法逆，事實上映射是不可逆的。