<b>本文講的是我是如何找回 Reddit 密碼的，</b>
<b></b>
黑掉整個星球，夥計們！
我真是一點自制力都沒有。
好在我對這一點頗有自知之明。我有意識地籌劃生活，是以盡管我跟海洛因上瘾的小白鼠一樣不成熟，偶爾還是可以搞定一些事情。
<a href="https://camo.githubusercontent.com/e2b41b5b16767dce9e8d1d0512f7a37dceeda463/68747470733a2f2f6d656469612e67697068792e636f6d2f6d656469612f674f483534656972695949774d2f67697068792e676966" target="_blank"></a>
嗯，簡直是浪費時間！
我逛 Reddit 浪費了很多時間。如果我想拖延點事情的話，常常會開一個新标簽頁然後一頭紮進 Reddit。但是有時我又得心無旁骛，減少幹擾。比如 2015 年 —— 我專注于提升自己的程式設計水準，而在 Reddit 閑逛就成了負擔。
我要搞個計劃控制我自己。
于是我就想：讓自己登陸不了賬号咋樣？
我是這樣做的：
我給賬号重設了随機密碼。叫朋友在某天把密碼用 email 發給我。這樣就可以萬無一失地讓自己上不了 Reddit 啦。（出于周全的考慮我還修改了找回密碼用的郵箱）。
本應有效，不過......
不幸的是，事實上朋友根本扛不住社會工程學。換句話說，他們「對你太好了」，如果你「求」他們要密碼，他們還是會發給你。
<a href="https://camo.githubusercontent.com/b798e84413ff6c6eac54ca30cea31572b252fa75/68747470733a2f2f6d656469612e67697068792e636f6d2f6d656469612f75423672735146673579507a572f67697068792e676966" target="_blank"></a>
不要這樣子看我。
失敗了幾次後，我得找個更可靠的辦法。谷歌搜尋了一會兒，我發現了這個：
看上去不錯。
完美！一個自動化且不需要朋友介入的方案！（我現在要疏遠大部分朋友，是以這一點很重要。）
看上去并不完善，不過管他呢，有個辦法就不錯了。
<a href="https://camo.githubusercontent.com/b16ce040a4a21d91429439c9f456b67e4c39dd39/68747470733a2f2f63646e2d696d616765732d312e6d656469756d2e636f6d2f6d61782f3830302f312a544f5549444f4952486956795355577434366e336d772e676966" target="_blank"></a>
我這樣堅持了一陣子：在工作日把密碼 email 給自己，周末收到密碼，在網際網路垃圾資訊中浪費時間，待下周開始就再鎖掉賬号。我印象中這一套效果不錯。
終于有一天寫代碼實在太忙了，我完全忘了這一回事。
我現在在 Airbnb 工作，薪酬頗豐。而且 Airbnb 剛巧有個巨大的測試元件。也就是說等待時間頗多，而等待就意味着可以上網摸魚。
我決定讨回舊賬号并找回 Reddit 密碼。
哦，不。這可不好。
我不記得我做過這一切，不過我當時肯定是太生自己的氣了，都把自己鎖到了 2018 年之後了。我還把郵件内容隐藏了，是以除非等到郵件發出去，我根本看不到内容。
我該怎麼辦？隻能建立一個 Reddit 賬号然後從頭開始嗎？但是這樣好麻煩啊。
我完全可以給 LetterMeLater 發郵件解釋自己并不是真的想這麼做。但是他們回信可能要好一會兒呢。而且你們都知道了，我是個急性子。這個網站看上去也不像是有客服團隊的樣子。更不要提寫這種郵件有多尴尬了。我開始頭腦風暴精心編造理由甚至扯到了去世的親人，試圖解釋為什麼需要看自己的郵件。
所有的選擇都不怎麼靠譜。那天晚上，從公司走到家一路上我都在思考自己的尴尬處境，突然就有靈感了。
搜尋欄
我用手機打開浏覽器 App 開始嘗試：
嗯。
好吧。是以（郵件）标題肯定是有索引的。那（郵件）内容呢？
試了幾個字母，果然沒錯。内容也是有索引的。記住：郵件内容裡面有我的密碼。
本質上這是一個執行子字元串檢索的界面。通過在搜尋欄輸入字元串，搜尋結果會告訴我密碼中是否有我輸入的子字元串。
萬事俱備。
我趕回自己的較高價的電梯大廈，放下包，取出筆記本電腦。
算法問題：已知函數 <code>substring?(str)</code>，它會根據輸入的密碼是否包含任何已知的子字元串來傳回 True 或 False。給定這個函數，寫一個可以推導出隐含密碼的算法。
讓我們好好想想。我記得我的密碼有這些特征：随機字元組成的長字元串，就像這樣子 <code>asgoihej2409g</code>。我很可能沒有用任何大寫字母（Reddit 并不要求密碼中一定有大寫字母），那麼先假設我沒用大寫字母。如果我真用了大寫字母，第一次嘗試失敗之後再将搜尋範圍擴大吧。
還有一個标題行，是檢索的字元串的一部分。而且郵件标題就是 "password"。
假設密碼長度為 6，就有了 6 個空位來放字元，有些字元會出現在标題行，有些不會。是以可以取出所有沒有出現在标題行的字元，逐一嘗試進行搜尋，肯定可以碰到一個獨一無二的字母，恰好出現在密碼中。就像是命運之輪遊戲。
繼續逐個字母進行嘗試，直到命中沒有出現在标題行的字元。這樣就找到了。
找到了第一個字母之後我仍然不知道它在字元串中的位置。不過我知道可以在它後面加一個不同的字元來構造一個更大的子字元串，直到再次命中。
有可能必需周遊字母表中每一個字元才能找到它。任何一個字母都可能是正确的，是以平均來說會命中中間位置的字母，如果字母表有 A 個字母，那麼可以預計每個字母平均會落到 A/2 處（假設主題字母較少且沒有超過兩個字元的重複組合）。
繼續建構子字元串，直到無法在末尾添加字元。
這還沒完 — 不過接近了，我落下了字元串的字首，因為我是随機選了個起點開始的。不過好辦，隻需要再重複一下之前的操作，方向反過來就好了。
搞定之後就可以着手重建密碼了。總而言之，我需要搞定 <code>L</code> 個字元，每個字元平均需要猜測 <code>A/2</code> 次（<code>A</code> 是字母表長度），加起來需要猜測 <code>A/2 * L</code> 次。
準确地說，我還得再猜測 <code>2A</code> 次來確定字元串兩端都到頭了。是以總數是 <code>A/2 * L + 2A</code>，提取公因數就是 <code>A(L/2 + 2)</code>.
假設密碼中有 20 個字元，字母表由 <code>a-z</code> 和 <code>0–9</code> 組成，總長度為 36。是以總疊代次數是 <code>36 * (20/2 + 2) = 36 * 12 = 432</code>。
可惡。
不過實際上是可行的。
<a href="https://camo.githubusercontent.com/846612b33f472083e225579e0772c6efeb017a2e/68747470733a2f2f6d656469612e67697068792e636f6d2f6d656469612f3131396356553139494363414b632f67697068792e676966" target="_blank"></a>
生活中的程式設計
首先：我得寫一個用戶端，用代碼控制搜尋框執行檢索。也就是我的子字元串「先知」。這個網站顯然沒有 API，我得直接爬網站。
搜尋用的 URL 模式看來就是簡單的檢索字元串，<code>www.lettermelater.com/account.php?**qe=#{query_here}**</code>。簡單吧。
開始寫腳本吧。我會用 Faraday 這個 gem 完成網絡請求，互動簡單，我比較熟悉。
首先寫一個 API 類。
當然，我可沒指望這就能用了，畢竟還沒有授權腳本登陸我的賬号。可以看到響應傳回了 302 重定向，還在 cookie 中提供了錯誤資訊。
（我當然不會把真的 cookie 貼在這兒。有意思的是看上去 cookie 在用戶端儲存了 user_id，這是個好信号。）
反複排除之後我發現需要 <code>code</code> 和 <code>user_id</code> 才能通過驗證…… 哎。
是以我把這些加到腳本中。（這隻是個用作示例的假 cookie）
拿到我的名字了，顯然登陸成功了！
爬資料搞定了，現在需要解析爬到的資料。幸運的是，這并不難 — 如果頁面中出現了 e-mail 就意味着搜尋命中了，是以隻需要找到這種情況下才會出現的字元串就好了。“password“ 在其他搜尋失敗的情況下并不會出現，是以就是它了。
API 類弄完了。現在完全可以用 Ruby 實作子字元串檢索了。
這個搞定之後就要用 stub 替換掉真正的 API 來琢磨算法了。發送 HTTP 請求會非常慢，還有可能在試驗的時候被限流。假設 stub API 是正确的，一旦搞定了剩下的算法部分，隻要換成真正的 API 可以用了。
下面就是内置了随機密碼的 stub API 了：
在測試時用 stub API 注入到類中。萬事俱備後再用真實的 API 來檢索真正的密碼。
下面就開始用 Apistub 類吧。先在較高的層次回憶一下算法流程，主要分為三步：
首先，找到第一個标題中沒有，卻在密碼中出現的字母。拿它作起點。
向前建構字元串，直到字元串尾。
反向建構字元串，直到字元串頭。
這樣就搞定了！
先做準備工作。要注入 API，還要把目前的密碼段置為空字元串。
接下來寫三個方法，就按照剛才計劃的做。
完美。現在剩下的都可以在私有方法中執行。
為了找到第一個字母，需要周遊字母表中的每個字元，條件是沒有出現在标題中。可以用 a-z 和 0-9 來構造字母表。用 Ruby 的範圍運算符（<code>..</code>）可以輕松搞定：
我偏向于把字母表随機打亂這樣可以避免密碼中字母的分布造成的偏差。這種情況下算法找到每個字元平均需要檢索 A/2 次，即使密碼并不是随機分布的。
還可以把标題定義為一個常量。
準備工作就是這些。下面該寫 <code>find_starting_letter</code> 了。這需要周遊每個候選字母（按照字母表順序，當然不能出現在标題中），直到第一個比對。
在測試階段看上去效果不錯：
下面是難點。
我會用遞歸來實作，因為結構更優雅。
上面的代碼簡潔明了。現在看看能不能和 stub API 工作。
贊！有了字尾，現在需要反向建構字元串。代碼應該看上去很相似。
實際上隻有兩行代碼有異：如何建構 <code>guess</code>，以及遞歸調用的名字。可以重構一下。
現在另一個調用可以簡化為：
來實戰一下：
漂亮。再加一些 print 語句和 log，<code>PasswordCracker</code> 就完成了。
接下來......就是見證奇迹的時刻。把 stub API 換成真實的 API，看看結果怎麼樣。
上天保佑……
<code>PasswordCracker.new(Api).crack!</code>
<a href="https://camo.githubusercontent.com/35a5ab907773165914c16bc1f70ee43c509be699/68747470733a2f2f63646e2d696d616765732d312e6d656469756d2e636f6d2f6d61782f3830302f312a4e522d79395774687448673444566a4c4477696b56412e676966" target="_blank"></a>
（三倍速）
Boom. 443 次疊代。
趕緊去 Reddit 試了一下，成功登入。
哇噢。
真的有效。
回憶一下原來那個計算疊代數的公式：<code>A(N/2 + 2)</code>。真正的密碼長度為 22，是以公式預計需要 <code>36 * (22/2 + 2) = 36 * 13 = 468</code> 次疊代。實際上用了 443 次疊代，是以估計值和觀測值的誤差在 5% 以内。
這就是數學。
<a href="https://camo.githubusercontent.com/c682551eba74d8fa6ee0e3d5dcde9922b643bc3d/68747470733a2f2f6d656469612e67697068792e636f6d2f6d656469612f32367842493733675771754342424344652f67697068792e676966" target="_blank"></a>
什麼鬼 鬼什麼 什鬼麼
真的有效
不用給客服寫尴尬的郵件了。重獲 Reddit 休閑時光。事實證明：程式設計——的确是——魔法。
（不過我又得找個新辦法讓自己暫時無法登入了。）
有了程式設計之技，我又可以在網際網路上揮霍時間了。感謝閱讀，如果喜歡請點贊！
—Haseeb
<b>原文釋出時間為：2017年5月10日</b>
<b>本文來自雲栖社群合作夥伴掘金，了解相關資訊可以關注掘金網站。</b>