破解 40 位 DVD CSS 流密碼
這是來自 Dan Boneh 的 Coursera Crypto 課程的成績單
https://www.coursera.org/learn/crypto/lecture/mQAkP/real-world-stream-ciphers
所以事實證明這很容易在大約兩點到十七點的時間裡打破。現在讓我告訴你怎麼做。所以假設你截取了電影，所以這裡我們有一個你想要解密的加密電影。所以假設這一切都是加密的，所以你不知道裡面有什麼。但是，恰好因為 DVD 加密使用 MPEG 文件，如果您知道明文的前綴，就會發生這種情況，假設這可能是 20 個字節。好吧，我們知道如果你把這兩個東西 XOR 在一起，換句話說，你在這裡做 XOR，你會得到 PRG 的初始段。因此，您將獲得 CSS 輸出的前 20 個字節，即此 PRG 的輸出。好的，現在這就是我們要做的。所以我們有輸出的前 20 個字節。現在我們執行以下操作。我們嘗試所有兩個到第一個 LFSR 的十七個可能值。好的？所以二到十七個可能的值。所以對於每個值，對於這兩個到 LFSR 的 17 個初始值中的每一個，我們將執行 LFSR 20 個字節，好嗎？因此，我們將從第一個 LFSR 生成 20 字節的輸出，假設——對於這兩個到十七個可能的設置中的每一個。現在，請記住我們擁有 CSS 系統的完整輸出。所以我們可以做的是我們可以獲取我們擁有的這個輸出。並從我們從第一個 LFSR 得到的 20 個字節中減去它，如果事實上我們對第一個 LFSR 的初始狀態的猜測是正確的，那麼我們應該得到的是第二個 LFSR 的前 20 個字節的輸出。正確的？因為這就是 CSS 系統的輸出的定義。好的？所以二到十七個可能的值。所以對於每個值，對於這兩個到 LFSR 的 17 個初始值中的每一個，我們將執行 LFSR 20 個字節，好嗎？因此，我們將從第一個 LFSR 生成 20 字節的輸出，假設——對於這兩個到十七個可能的設置中的每一個。現在，請記住我們擁有 CSS 系統的完整輸出。所以我們可以做的是我們可以獲取我們擁有的這個輸出。並從我們從第一個 LFSR 得到的 20 個字節中減去它，如果事實上我們對第一個 LFSR 的初始狀態的猜測是正確的，那麼我們應該得到的是第二個 LFSR 的前 20 個字節的輸出。正確的？因為這就是 CSS 系統的輸出的定義。好的？所以二到十七個可能的值。所以對於每個值，對於這兩個到 LFSR 的 17 個初始值中的每一個，我們將執行 LFSR 20 個字節，好嗎？因此，我們將從第一個 LFSR 生成 20 字節的輸出，假設——對於這兩個到十七個可能的設置中的每一個。現在，請記住我們擁有 CSS 系統的完整輸出。所以我們可以做的是我們可以獲取我們擁有的這個輸出。並從我們從第一個 LFSR 得到的 20 個字節中減去它，如果事實上我們對第一個 LFSR 的初始狀態的猜測是正確的，那麼我們應該得到的是第二個 LFSR 的前 20 個字節的輸出。正確的？因為這就是 CSS 系統的輸出的定義。我們將執行 LFSR 20 個字節，好嗎？因此，我們將從第一個 LFSR 生成 20 字節的輸出，假設——對於這兩個到十七個可能的設置中的每一個。現在，請記住我們擁有 CSS 系統的完整輸出。所以我們可以做的是我們可以獲取我們擁有的這個輸出。並從我們從第一個 LFSR 得到的 20 個字節中減去它，如果事實上我們對第一個 LFSR 的初始狀態的猜測是正確的，那麼我們應該得到的是第二個 LFSR 的前 20 個字節的輸出。正確的？因為這就是 CSS 系統的輸出的定義。我們將執行 LFSR 20 個字節，好嗎？因此，我們將從第一個 LFSR 生成 20 字節的輸出，假設——對於這兩個到十七個可能的設置中的每一個。現在，請記住我們擁有 CSS 系統的完整輸出。所以我們可以做的是我們可以獲取我們擁有的這個輸出。並從我們從第一個 LFSR 得到的 20 個字節中減去它，如果事實上我們對第一個 LFSR 的初始狀態的猜測是正確的，那麼我們應該得到的是第二個 LFSR 的前 20 個字節的輸出。正確的？因為這就是 CSS 系統的輸出的定義。所以我們可以做的是我們可以獲取我們擁有的這個輸出。並從我們從第一個 LFSR 得到的 20 個字節中減去它，如果事實上我們對第一個 LFSR 的初始狀態的猜測是正確的，那麼我們應該得到的是第二個 LFSR 的前 20 個字節的輸出。正確的？因為這就是 CSS 系統的輸出的定義。所以我們可以做的是我們可以獲取我們擁有的這個輸出。並從我們從第一個 LFSR 得到的 20 個字節中減去它，如果事實上我們對第一個 LFSR 的初始狀態的猜測是正確的，那麼我們應該得到的是第二個 LFSR 的前 20 個字節的輸出。正確的？因為這就是 CSS 系統的輸出的定義。***現在，事實證明，查看 20 字節序列，很容易判斷這個 20 字節序列是否來自 25 位 LFSR。***如果沒有，那麼我們知道我們對 17 位 LFSR 的猜測是不正確的，然後我們繼續對 17 位 LFSR 進行下一個猜測，然後再進行下一個猜測，依此類推。直到我們最終達到 17 位 LFSR 的正確初始狀態，然後我們將真正得到，我們將看到作為 25 位 LFSR 的候選輸出得到的 20 個字節實際上是一個可能的輸出對於 25 位 LFSR。然後，我們不僅學習了 17 位 LFSR 的正確初始狀態，我們還將學習了 25 位 LFSR 的正確初始狀態。然後我們可以預測 CSS 的剩餘輸出，當然，使用它，
我不明白他用粗體表示的句子是什麼意思——“現在，事實證明，看一個 20 字節的序列，很容易判斷這個 20 字節的序列是來自 25 位 LFSR 還是不是。”
您如何判斷 20 字節序列是否來自 25 位 LFSR？
有一種Berlekamp-Massey算法可以為給定的二進制序列構造最短的 LFSR。
對於長度的 LFSR $ L $ 給定 $ 2L $ 從 LFSR 輸出序列，建構 LFSR 就足夠了。要構造一個 25 位的 LSFR，50 位就足夠了。請注意，該算法不需要知道抽頭。它只是構造可以產生給定序列的最小 LFSR。
查看 20 字節（160 位），您可以確保剩餘的 110 位是從 LFSR 輸出的。我們不期望以微不足道的 $ 1/2^{110} $ LFSR 成功產生隨機位的機率。
研究 LFSR 的