Скрипт - scrypt - Wikipedia

скрипт
Жалпы
Дизайнерлер	Колин перцивалы
Алғаш жарияланған	2009
Шифр бөлшектері
Дайджест өлшемдері	айнымалы
Блок өлшемдері	айнымалы
Дөңгелек	айнымалы

Жылы криптография, скрипт («ess crypt» деп оқылады^[1]) парольге негізделген кілт шығару функциясы бастапқыда Колин Персивал жасаған Тарснап желілік резервтік қызмет.^[2] Алгоритм оны ауқымды орындау үшін қымбатқа түсу үшін арнайы жасалған жабдықтың арнайы шабуылдары үлкен көлемдегі жадты қажет ету арқылы. 2016 жылы scrypt алгоритмі жарияланды IETF сияқты RFC 7914. А ретінде скрипттің жеңілдетілген нұсқасы қолданылады жұмыс дәлелі саны бойынша схема криптовалюта, алдымен TenFrix-те ArtForz деп аталатын белгісіз бағдарламашы, содан кейін Fairbrix және Litecoin көп ұзамай.^[3]

Кіріспе

Құпия сөз негізіндегі кілт шығару функциясы (парольге негізделген KDF) әдетте есептеу қарқынды болу үшін есептелген, сондықтан оны есептеу салыстырмалы түрде ұзақ уақытты алады (бірнеше жүз миллисекундтар бойынша). Заңды пайдаланушылар функцияны тек бір операцияға бір рет орындауы керек (мысалы, аутентификация), сондықтан қажет уақыт шамалы. Алайда қатал шабуылға операцияны миллиардтаған рет жасау қажет болуы мүмкін, сол кезде уақыт талаптары маңызды және идеалды түрде тыйым салады.

Алдыңғы парольге негізделген KDF (танымал сияқты) PBKDF2 бастап RSA зертханалары ) ресурстарға деген салыстырмалы түрде төмен сұраныстарға ие, яғни оларды орындау үшін күрделі жабдықтар немесе өте көп жад қажет емес. Сондықтан олар жабдықта оңай және арзан түрде жүзеге асырылады (мысалы ASIC немесе тіпті FPGA ). Бұл жеткілікті ресурстарға ие шабуылдаушыға алгоритмнің жүздеген, тіпті мыңдаған іске асыруларын құруда және әр іздеуде кілттік кеңістіктің әр түрлі ішкі жиынын құра отырып, ауқымды параллель шабуыл жасауға мүмкіндік береді. Бұл қатал шабуыл жасау үшін қажет уақытты қол жетімді іске асыру санына бөледі, мүмкін оны ақылға қонымды мерзімге дейін жеткізеді.

Scrypt функциясы алгоритмнің ресурстарға деген қажеттілігін жоғарылату арқылы мұндай әрекеттерді болдырмауға арналған. Нақтырақ айтсақ, алгоритм басқа парольге негізделген KDF-пен салыстырғанда үлкен жадыны пайдалануға арналған,^[4] аппараттық жабдықтаудың мөлшері мен құнын әлдеқайда қымбатқа түсіру, сондықтан шабуылдаушының белгілі бір қаржы ресурстарына қолдануы мүмкін параллелизм мөлшерін шектеу.

Шолу

Скрипттің үлкен жадының қажеттілігі үлкен векторынан шығады жалған кездейсоқ алгоритмнің бөлігі ретінде жасалатын биттік жолдар. Вектор құрылғаннан кейін оның элементтеріне жалған кездейсоқ тәртіпте қол жетімді және алынған кілт шығару үшін біріктіріледі. Тікелей іске асыру үшін қажет болған жағдайда оған қол жеткізу үшін бүкіл векторды жедел жадыда сақтау қажет.

Вектор элементтері алгоритмдік жолмен жасалатын болғандықтан, әр элементті жасауға болатын еді ұшу кезінде қажет болған жағдайда, бір уақытта тек бір элементті жадта сақтайды, сондықтан жадқа деген қажеттілікті едәуір азайтады. Алайда, әр элементтің генерациясы есептеудің қымбаттығына арналған және функцияны орындау барысында элементтерге бірнеше рет қол жетеді деп күтілуде. Осылайша, есте сақтаудың үлкен қажеттіліктерінен құтылу үшін жылдамдықтың едәуір келісімі бар.

Мұндай уақыт пен жадты айырбастау компьютерлік алгоритмдерде жиі кездеседі: жылдамдықты көбірек жадыны пайдалану есебінен көбейтуге болады, немесе жадқа деген қажеттілік көп операцияларды орындау және ұзақ уақытты алу кезінде азаяды. Скрипттің негізгі мақсаты - бұл келісімді екі бағытта әдейі қымбатқа айналдыру. Осылайша, шабуылдаушы көптеген ресурстарды қажет етпейтін (сондықтан оларды шектеулі шығындармен параллельдеуге болады), бірақ өте баяу жұмыс жасайтын немесе тезірек жұмыс істейтін, бірақ есте сақтау қабілеті өте үлкен, сондықтан қымбат тұратын бағдарламаны қолдана алады. параллельдеу.

Алгоритм

Алгоритм келесі параметрлерді қамтиды:

Құпия фраза - хэштелетін символдар қатары.
Тұз - Хэштен қорғану үшін оны өзгертетін символдар қатары Радуга үстелі шабуылдар
N - процессор / жады шығынының параметрі.
p - параллельдеу параметрі; р satisf-ны қанағаттандыратын оң бүтін сан (2)³²- 1) * hLen / MFLen.
dkLen - алынған кілттің октеттеріндегі шығыс ұзындығы; dkLen ying-ті қанағаттандыратын оң бүтін сан (2³²- 1) * сағ.
r - оқшаулау параметрі, ол жүйелі жадтың өлшемі мен өнімділігін дәл келтіреді. 8 әдетте қолданылады.
hLen - хэш функциясының октеттердегі ұзындығы (SHA256 үшін 32).
MFlen - араластыру функциясының шығуының октеттердегі ұзындығы (SMix төменде). RFC7914 стандартында r * 128 ретінде анықталған.

Функция скрипт Кірістер:      Құпия сөз: байт таңбалар тізбегі      Тұз: байт кездейсоқ тұз      CostFactor (N): бүтін сан CPU / жад құны параметрі - 2 қуат болуы керек (мысалы, 1024)      BlockSizeFactor (r): бүтін сан блоктау параметрі (8 жиі қолданылады)      Параллелизация факторы (p): бүтін Параллельдеу параметрі. (1..2³²-1 * hLen / MFlen)      DesiredKeyLen: бүтін сан Қажетті кілт ұзындығы байтпен   Шығарылым:      DerivedKey: байт массив байт, DesiredKeyLen ұзақ   Қадам 1. Қымбат тұзды шығарыңыз   blockSize ← 128 * BlockSizeFactor // SMix араластыру функциясының ұзындығы (байтпен) (мысалы, 128 * 8 = 1024 байт)   Бастапқы 128 * BlockSizeFactor * p байт деректерін жасау үшін PBKDF2 пайдаланыңыз (мысалы, 128 * 8 * 3 = 3072 байт)   Нәтижені массив ретінде қарастырыңыз б элементтер, әр жазба блоктау байт (мысалы, 3 элемент, әрқайсысы 1024 байт)   [B₀... B_{p − 1}] ← PBKDF2_HMAC-SHA256(Құпия фраза, Тұз, 1, blockSize * ParallelizationFactor) Әр блокты араластырыңыз B Costfactor пайдалану уақыты ROMix функциясы (әр блокты қатарластыруға болады)   үшін мен ← 0 дейін p-1 істеу      B_мен ← ROMix (B_мен, CostFactor) В элементтері - бұл біздің жаңа «қымбат» тұз   қымбат Тұз ← B₀∥B₁∥B₂∥ ... ∥B_p-1  // мұндағы ∥ - біріктіру    Қадам 2. PBKDF2 көмегімен байттардың қажетті санын шығарыңыз, бірақ біз қымбат тұратын тұзды қолданамыз   қайту PBKDF2_HMAC-SHA256(Құпия сөз, қымбат тұз, 1, DesiredKeyLen);

Қайда PBKDF2 (P, S, c, dkLen) белгісі анықталған RFC 2898, мұндағы с - қайталану саны.

Бұл белгіні қолданады RFC 7914 c = 1 мәнімен PBKDF2 қолданысын анықтау үшін.

Функция ROMix (Блок, қайталаулар) Жасаңыз Қайталау дана X   X ← Блок үшін мен ← 0 дейін Қайталау − 1 істеу      V_мен ← X X ← BlockMix (X) үшін мен ← 0 дейін Қайталау − 1 істеу      j ← Integerify (X) моделінің қайталануы X ← BlockMix (X xor V_j)   қайту X

Қайда RFC 7914 анықтайды Бүтіндеу (X) Х-тің соңғы 64 байтын а ретінде түсіндіру нәтижесінде кішкентай ендиан бүтін A₁.

Қайталау N қуатына 2-ге тең болғандықтан, тек бірінші Арасында төбелік байт (N / 8) соңғы 64 байт X, а деп түсіндіріледі кішкентай ендиан бүтін A₂, есептеу үшін қажет Integerify (X) mod Iterations = A₁ мод Итерация = A₂ модерация.

Функция BlockMix (B): B блогы r 128 байтты бөліктер (бұл 2r 64 байттық бөліктерге тең)    r ← ұзындығы (B) / 128; B-ді 2r 64 байттық бөліктер жиымы ретінде қарастырыңыз    [B₀... B_2р-1] ← B X ← B_{2r − 1}    үшін мен ← 0 дейін 2r − 1 істеу        X ← Salsa20 / 8 (X xor B.)_мен)  // Salsa20 / 8 хэштері 64 байттан 64 байтқа дейін        Y_мен ← X қайту ← Y₀∥Ж₂∥ ... ∥Ж_{2r − 2} . Y₁∥Ж₃∥ ... ∥Ж_{2r − 1}

Қайда Сальса20 / 8 дегеннің 8 раундтық нұсқасы 20.

Криптовалюта қолданады

Скрипт көптеген криптовалюталарда а ретінде қолданылады жұмыс дәлелі алгоритм. Ол алғаш рет Tenebrix үшін енгізілді (2011 жылдың қыркүйегінде шығарылды) және негіз болды Litecoin және Dogecoin, ол сонымен қатар өзінің скрипт алгоритмін қабылдады.^[5]^[6] Тау-кен өндірісі криптовалюта скриптті қолданатын графикалық блоктарда жиі орындалады (Графикалық процессорлар ), өйткені графикалық процессорлар процессормен салыстырғанда айтарлықтай қуаттылыққа ие (кейбір алгоритмдер үшін).^[7] Бұл 2013 жылдың қараша және желтоқсан айларында осы валюталардың қымбаттауына байланысты жоғары деңгейлі графикалық процессорлардың жетіспеушілігіне әкелді.^[8]

Мамыр 2014 ж., Мамандандырылған ASIC Тау-кен жабдықтары скриптке негізделген криптовалюта үшін қол жетімді.^{[дәйексөз қажет ]}

Сондай-ақ қараңыз

Кілттерді шығару функциясы
Аргон2, құпия сөзді шайқау конкурсының жеңімпазы
крипт, құпия сөзді сақтау және тексеру схемасы
PBKDF2, кеңінен қолданылатын стандартты парольге негізделген кілттерді шығару функциясы
bcrypt, құпия сөзді хэштеу функциясын қолдану Blowfish
Уақыттың кеңістігі

Әдебиеттер тізімі

^ «Колин Персивал Twitter-де».
^ «Tarsnap веб-сайтындағы скрипт парағы». Алынған 21 қаңтар 2014.
^ Алек Лю. «Биткойннан тыс: ең перспективалы криптовалютаға нұсқаулық».
^ Жадының қиын функциялары арқылы күшті туындыны шығару, Colin Percival
^ Андреас М. Антонопулос (3 желтоқсан 2014). Bitcoin-ті игеру: Сандық криптовалюталардың құлпын ашу. O'Reilly Media. 221, 223 беттер. ISBN 9781491902646.
^ «Криптовалютаның тарихы». Архивтелген түпнұсқа 2016 жылғы 11 маусымда. Алынған 27 маусым 2014.
^ Роман Гуэлфи-Гиббс. Radeon 7950 үшін Litecoin Scrypt тау-кен конфигурациясы. Amazon Digital Services.
^ Джоэль Хруска (10 желтоқсан 2013). «Litecoin тау-кен саласындағы қарқынды өсу графикалық карта тапшылығына әкеледі». ExtremeTech.

Сыртқы сілтемелер

[1] «Колин Персивал Twitter-де».

[2] «Tarsnap веб-сайтындағы скрипт парағы». Алынған 21 қаңтар 2014.

[3] Алек Лю. «Биткойннан тыс: ең перспективалы криптовалютаға нұсқаулық».

[4] Жадының қиын функциялары арқылы күшті туындыны шығару, Colin Percival

[5] Андреас М. Антонопулос (3 желтоқсан 2014). Bitcoin-ті игеру: Сандық криптовалюталардың құлпын ашу. O'Reilly Media. 221, 223 беттер. ISBN 9781491902646.

[6] «Криптовалютаның тарихы». Архивтелген түпнұсқа 2016 жылғы 11 маусымда. Алынған 27 маусым 2014.

[7] Роман Гуэлфи-Гиббс. Radeon 7950 үшін Litecoin Scrypt тау-кен конфигурациясы. Amazon Digital Services.

[8] Джоэль Хруска (10 желтоқсан 2013). «Litecoin тау-кен саласындағы қарқынды өсу графикалық карта тапшылығына әкеледі». ExtremeTech.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]