JK 觸發器的非線性
在Encryption Schemes for Computer Confidentiality中，Pless 描述瞭如何將 JK 觸發器用作線性回饋移位寄存器的非線性組合器。這個生成器壞了，因為 JK 觸發器不是相關免疫的，但我的問題涉及 JK 函式本身的基本非線性：你如何測量它的非線性？例如，我們知道具有最大非線性的布爾函式是彎曲函式，它與所有仿射函式的距離最遠。然後我們有像 XOR 這樣的線性函式，那麼 JK 觸發器在哪裡適合這個頻譜呢？
沒有辦法將JK 觸發器簡化為布爾函式，更不用說 2 輸入布爾函式了。JK 觸發器是一個 3 輸入塊，除了輸入之外還有一個時鐘輸入 $ J $ 和 $ K $ . 它的輸出不是這些輸入的布爾函式，因為過去的輸出對未來的輸出很重要。
如果我們想使用布爾函式對 JK 觸發器建模，我們可以通過多種方式來實現，包括兩個相同的 3 輸入函式 $ Q(I,B,C)=(I\cdot B\cdot C)|\bar B $ ， 在哪裡 $ I $ 是 $ J $ 對於一個功能和 $ K $ 對於另一個， $ B $ 是另一個函式的輸出，並且 $ C $ 是時鐘，根據這個示意圖：
了解初始狀態 $ Q $ , 和輸入 $ J $ , $ K $ , $ C $ ，這允許預測未來 $ Q $ , 除了一些輸入 $ C $ 幾乎同時發生變化 $ J $ 或者 $ K $ .
這篇文章考慮了一個具有單輸出的 JK 觸發器，它與其他兩個顯式輸入的源共享其時鐘輸入（隱式） $ J $ 和 $ K $ . 給出的模型是：
國家（注 $ R_n $ 在文章中）的輸出 $ Q $ JK觸發器在某個時鐘週期 $ n $ 是
$$ R_{n+1}=((J\oplus \bar K)\cdot R_n)\oplus J $$ （可以從 JK 觸發器的任何適當模型推導出來，包括上述模型作為兩個布爾函式）。因此，在現代論述中，在這種時鐘配置中使用 JK 觸發器的任何東西都可以在非線性回饋移位寄存器的框架中輕鬆表達。
在文章的共享時鐘配置中，上面給出的JK觸發器的回饋函式是一個3輸入1輸出的布爾函式 $ F(J,K,R)=((J\oplus \bar K)\cdot R)\oplus J $ ，其中額外的輸入 $ R $ 是之前的輸出。真值表為 $ F $ 可以從正常濃縮 $ 2^3 $ 條目
$$ \begin{align*} J&K&F\ 0&0&R&\text{ unchanged}\ 0&1&0&\text{ clear}\ 1&0&1&\text{ set}\ 1&1&\bar R&\text{ toggle}\ \end{align*} $$ 這個功能 $ F $ 是平衡的（即，一半 $ 2^3 $ 輸出為 1)，並且 $ F(J,K,R)\oplus R $ 也是平衡的。 $ F $ 對於每個輸入都是非線性的（也就是說，輸出與任何輸入的 XOR 不是其他輸入的函式）。
$ F $ 不是相關免疫的：輸出偏向於 $ J $ , 並且朝向 $ \bar K $ . 這確實允許在組合 LFSR 的情況下進行攻擊，但是替換 $ F $ 任何 3 輸入布爾函式都無法改善這一點；列舉 256 個這樣的函式，我們會發現輸出存在一些問題（從最差到最少排序）：
- 嚴重偏見（這就是為什麼我們想要 $ F $ 均衡）;
- 與之前的輸出嚴重相關（這就是我們想要 $ F(J,K,R)\oplus R $ 均衡）;
- 與兩個輸入之一的極性和時鐘延遲相等，使用Berlekampf-Massey 算法可以有效地預測（作為 LFSR）；
- 在極性範圍內和兩個輸入的 XOR 的時鐘延遲相等，這可以通過相同的方法有效地預測，因為任何兩個 LFSR 的輸出的 XOR 與另一個大小最多等於總和的 LFSR 的輸出相同兩個 LFSR 的大小；
- 與 JK 觸發器案例中的輸入相關。
注意：我對彎曲和半彎曲函式的定義不熟悉，不會嘗試在哪里分類 $ F $ 屬於，但從彎曲和半彎曲的定義來看，這應該是微不足道的，不管那是什麼。
注意：JK 觸發器似乎是Frederik Armknecht 和 Matthias Krause 在Algebraic Attacks on Combiners with Memory (Crypto 2003)中研究的框架中最簡單的具有記憶體的兩輸入組合器之一。
