Scrypt

scrypt（念作「ess crypt」），是加拿大計算機科學家暨計算機安全研究人員科林·珀西瓦爾（Colin Percival）於2009年所發明的密鑰派生函數，當初設計用在他所創立的Tarsnap服務上。設計時考慮到大規模的客制硬件攻擊而刻意設計需要大量記憶體運算。2016年，scrypt算法發布在RFC 7914。scrypt 的簡化版被用在數個密碼貨幣的工作量證明（Proof-of-Work）上，首次由一位匿名程序員 ArtForz 在 Tenebrix 中實現，隨後 Fairbrix 和 Litecoin 也很快採用了該方案。

概述

Scrypt 需要使用大量記憶體的原因來自於產生大量偽隨機性（英語：pseudorandom）資料作為算法計算的基礎。一旦這些資料被產生後，算法將會以偽隨機性的順序讀取這些資料產生結果。因此最直接的實做方式將會需要大量記憶體將這些資料儲存在記憶體內供算法計算。

另外一方面，由於偽隨機性資料是透過算法產生，在實做上也可以在需要存取時再計算以降低記憶體使用量。但由於計算成本很高，這個實做方法將大幅降低算法的速度。

這就是scrypt設計時考慮到的時空權衡，攻擊者可以使用後者的方法但計算速度很慢，或是用前者的方法但因記憶體成本而難以大規模平行化。

基於密碼的密鑰派生函數（密碼基 KDF）通常設計為計算密集型的，以便計算過程需要相對較長的時間（例如幾百毫秒）。合法用戶每次操作（例如身份驗證）只需執行一次該函數，因此所需的時間可以忽略不計。然而，暴力破解攻擊可能需要執行數十億次操作，在這種情況下，所需的時間變得顯著，並且理想情況下，應該是禁止性的。

之前的基於密碼的 KDF（例如 RSA 實驗室的流行 PBKDF2）資源需求相對較低，這意味着它們不需要複雜的硬件或大量內存來執行。因此，它們可以輕鬆且廉價地在硬件中實現（例如在 ASIC 或甚至 FPGA 上）。這使得攻擊者可以利用足夠的資源，通過在硬件中構建數百甚至數千個該算法的實現，並讓每個實現搜索密鑰空間的不同子集，從而發起大規模並行攻擊。這種方法通過可用實現的數量將完成暴力破解攻擊所需的時間分攤，可能將其縮短到合理的時間範圍。

scrypt 函數的設計旨在通過提高算法的資源需求來阻礙這種攻擊。具體而言，該算法設計為使用大量內存，相較於其他基於密碼的 KDF，使硬件實現的大小和成本大大增加，從而限制了攻擊者在給定財務資源的情況下可以使用的並行性。

密碼貨幣上的使用

Scrypt 被用在數個密碼貨幣的工作量證明算法上（更準確地說，是作為 Hashcash 工作量證明算法中的哈希函數）。首先被 Tenebrix 所使用（2011年9月)，而後被萊特幣（Litecoin）與狗狗幣（Dogecoin）所採用。因GPU在計算使用scrypt的密碼貨幣較CPU有效率，這導致了高階顯卡在2013年年底的短缺。

2014年起，市場上已經有使用ASIC計算scrypt算法的挖礦機。