Скрипт

скрипт

Умумӣ		Тарроҳон	Колин Персивал
Бори аввал нашр шуд	2009
Тафсилоти шифр
Андозаҳои ҳаҷм	тағйирёбанда
Андозаи блокҳо	тағйирёбанда
Давраҳо	тағйирёбанда

Портали Free and open-source software

Дар криптография, scrypt (талаффузи "ess crypt" ) як функсияи ҳосилкунии калид дар асоси рамз аст, ки аз ҷониби Колин Персивал моҳи марти соли 2009 барои хидмати нусхабардории онлайни Tarsnap сохта шудааст. Алгоритм махсус барои он тарҳрезӣ шудааст, ки иҷрои ҳамлаҳои сахтафзори фармоишии калонмиқёсро бо дархости миқдори зиёди хотира гарон гардонад. Дар соли 2016, алгоритми scrypt аз ҷониби IETF ҳамчун RFC 7914 нашр карда шуд. Гузинаҳои содаи scrypt ҳамчун схемаи исботи кор аз ҷониби як гурӯҳи рамзарзҳо корбаст мешавад, ки аввалин маротиба аз ҷониби як барномасози беном бо номи ArtForz дар Tenebrix амалӣ карда мешавад ва сипас Fairbrix ва Litecoin ба низ азо истифода мекунанд.

Муқаддима

Функсияи истихроҷи калидҳо дар асоси рамз(КDF-и асосёфта бар гузарвожа) одатан барои пуршиддат кардани раванди ҳисоббарорӣ тарҳрезӣ шудааст, ки барои ҳисоб кардани он вақти нисбатан тӯлонӣ лозим мешавад(масалан, бо тартиби чандсад миллисония). Корбарони қонунӣ бояд ин вазифаро танҳо як маротиба дар як амалиёт иҷро кунанд (масалан, асолатсанҷӣ) ва аз ин рӯ вақти зарурӣ ночиз мебошад. Бо ин нигоҳ накарда, ҳамлаи бераҳмона эҳтимол бояд миллиардҳо маротиба амалиётро иҷро кунад, ки дар он талаботи вақт назаррас идеалӣ, пешгирикунанда мешаванд.

KDF-ҳои қаблии ба рамз асосёфта (ба монанди маъмули PBKDF2 аз RSA Laboratories ) талаботи нисбатан ками захираҳоро доранд, яъне онҳо барои иҷроиш сахтафзори мукаммал ё хотираи зиёдеро талаб намекунанд. Аз ҳамин сабаб, онҳоро метавон дар сахтафзор ба осонӣ ва арзон татбиқ кард (масалан, дар ASIC ё ҳатто FPGA). Ин ба рахнагар бо захираҳои кофӣ имкон медиҳад, ки як ҳамлаи мувозии васеъмиқёсеро тавассути сохтани садҳо ва ҳатто ҳазорҳо амалисозии алгоритм дар сахтафзор оғоз кунад ва ҳар як зергурӯҳи дигари фазои калидиро мавриди ҷустуҷӯ қарор диҳад. Ин вақти кофиро барои анҷом додани таҳоҷуми бераҳмона ба шумораи татбиқҳои мавҷуда тақсим мекунад ва эҳтимолан онро ба як чаҳорчӯбаи вақти мувофиқ бурда мерасонад.

Функсияи scrypt барои монеъ шудан ба чунин кӯшишҳо тавассути баланд бардоштани талаботи захираҳои алгоритм тарҳрезӣ карда шудааст. Ба вижа, алгоритм барои истифодаи миқдори зиёди хотира дар муқоиса бо дигар KDF-ҳои ба гузарвожа асосёфта тарҳрезӣ карда шудааст, ки андоза ва арзиши татбиқи сахтафзорро хеле гаронтар мекунад ва аз ин рӯ миқдори параллелизмро, ки ҳамлакунанда истифода мебарад, маҳдуд мекунад, барои микдори муайяни захираҳои молӣ.

Баррасӣ

Талаботи калони хотираи scrypt аз як вектори калони сатрҳои псевдорандоми бит, ки ҳамчун як қисми алгоритм тавлид мешаванд, бармеоянд. Пас, аз тавлиди вектор, ба унсурҳои он бо тартиби псевдорандом дастрасӣ пайдо мекунанд ва барои тавлиди калиди ҳосилшуда муттаҳид мешаванд. Татбиқи бевосита бояд тамоми векторро дар RAM, то вақти лозима ва дастрас нигоҳ дорад.

Азбаски унсурҳои вектор ба таври алгоритмӣ тавлид мешаванд, ҳар як элементро метавон дар ҳолати зарурӣ дар парвоз тавлид кард, танҳо як элементро дар ҳофиза дар як вақт нигоҳ медорад ва аз ин рӯ, талаботи ҳофизаро ба таври назаррас коҳиш медиҳад. Бо вуҷуди ин, тавлиди ҳар як элемент аз ҷиҳати ҳисоббарорӣ гарон аст ва интизор меравад, ки ба унсурҳо дар давоми иҷрои функсия чанд маротиба дастрасӣ пайдо кунанд. Ҳамин тавр, барои бартараф кардани талаботи ҳофизаи калон як мубодилаи назаррас дар суръат вуҷуд дорад.

Ин гуна тавофуқӣ замон ва хотира аксар вақт дар алгоритмҳои компютерӣ мавҷуд аси: суръатро метавон аз ҳисоби истифодаи бештари ҳофиза зиёд кард ё талаботи ҳофизаро бо арзиши иҷрои амалиёти бештар ва вақти тӯлонӣ коҳиш дод. Идеяи пушти scrypt ин аст, ки дидаву дониста ин савдоро дар ҳар ду самт гарон кунад. Ҳамин тариқ, ҳамлакунанда метавонад татбиқеро истифода барад, ки захираҳои зиёдро талаб намекунад (ва аз ин рӯ онро метавон бо хароҷоти маҳдуд ба таври оммавӣ мувозӣ сохт), аммо хеле суст кор мекунад ё татбиқеро истифода мебарад, ки тезтар кор мекунад, талаботи ҳозизаи хеле калон дорад ва бинобар ин мувозӣ сохтани он гаронтар тамом мешавад.

Алгоритм

Function scrypt
   Inputs: This algorithm includes the following parameters:
      Passphrase:                Bytes    string of characters to be hashed
      Salt:                      Bytes    string of random characters that modifies the hash to protect against Rainbow table attacks
      CostFactor (N):            Integer  CPU/memory cost parameter – Must be a power of 2 (e.g. 1024)
      BlockSizeFactor (r):       Integer  blocksize parameter, which fine-tunes sequential memory read size and performance. (8 is commonly used)
      ParallelizationFactor (p): Integer  Parallelization parameter. (1 .. 232-1 * hLen/MFlen)
      DesiredKeyLen (dkLen):     Integer  Desired key length in bytes (Intended output length in octets of the derived key; a positive integer satisfying dkLen ≤ (232− 1) * hLen.)
      hLen:                      Integer  The length in octets of the hash function (32 for SHA256).
      MFlen:                     Integer  The length in octets of the output of the mixing function (SMix below). Defined as r * 128 in RFC7914.
   Output:
      DerivedKey:                Bytes    array of bytes, DesiredKeyLen long

   Step 1. Generate expensive salt
   blockSize ← 128*BlockSizeFactor  // Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)

   Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)
   Treat the result as an array of p elements, each entry being blocksize bytes (e.g. 3 elements, each 1024 bytes)
   [B0...Bp−1] ← PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor)

   Mix each block in B Costfactor times using ROMix function (each block can be mixed in parallel)
   for i ← 0 to p-1 do
      Bi ← ROMix(Bi, CostFactor)

   All the elements of B is our new "expensive" salt
   expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1  // where ∥ is concatenation
 
   Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated
   return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

Дар ин ҷо PBKDF2(P, S, c, dkLen) дар RFC 2898 муайян карда шудааст, ки дар он c шумораи такрорист.

Ин нишондод аз тарафи RFC 7914 барои муайян кардани корбурди PBKDF2 бо c = 1 истифода бурда мешавад.

Function ROMix(Block, Iterations)

   Create Iterations copies of X
   X ← Block
   for i ← 0 to Iterations−1 do
      Vi ← X
      X ← BlockMix(X)

   for i ← 0 to Iterations−1 do
      j ← Integerify(X) mod Iterations 
      X ← BlockMix(X xor Vj)

   return X

Дар он ҷо RFC 7914 Integerify(X) -ро дар натиҷаи баргардони 64 бити охирини X ҳамчун адади бутуни little-endian A ₁ муайян карда мешавад.

Азбаски Итератсияҳои 2 ба қудрати N баробар мебошанд, танҳо дар байни 64 бити охири X, ки ҳамчун адади бутуни little-endian-и A ₂ тафсир карда мешаванд, барои ҳисобкунии Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations лозим ст

Function BlockMix(B):

    The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)
    r ← Length(B) / 128;

    Treat B as an array of 2r 64-byte chunks
    [B0...B2r-1] ← B

    X ← B2r−1
    for i ← 0 to 2r−1 do
        X ← Salsa20/8(X xor Bi)  // Salsa20/8 hashes from 64-bytes to 64-bytes
        Yi ← X

    return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

Дар ин ҷо Salsa20/8 версияи 8-давраи Salsa20 аст.

Истифодаи рамзарзҳо

Скрипт дар бисёре аз рамзарзҳо ҳамчун алгоритми исботи кор истифода бурда мешавад (аниқтараш, ҳамчун функсияи hash дар алгоритми исботи кор Hashcash ). Он бори аввал дар Tenebrix роҳандозӣ шудааст (дар моҳи сентябри соли 2011 бароварда шуд) ва ҳамчун асос барои Litecoin ва Dogecoin хидмат кард, ки алгоритми scrypt-и худро низ қабул кард. Истихроҷи рамзарзҳо, ки scrypt-ро истифода мебаранд, аксар вақт дар воҳидҳои пардозиши графикӣ ( GPU ) анҷом дода мешавад, зеро Воҳидҳои пардозиши графикӣ дар муқоиса бо CPU ба таври назаррас қудрати пардозиш доранд (барои баъзе алгоритмҳо). Ин ба камбуди GPU-ҳои баландсифат дар натиҷаи афзоиши нархи ин рамзарзҳо дар моҳҳои ноябр ва декабри соли 2013-ум оварда расонид

Моҳи майи соли 2014, сахтафзори махсуси истихроҷи ASIC барои рамзарзҳо дар асоси скрипт дастрас шуд. </link>

Судмандӣ

судмандии скрипт дар моҳи майи соли 2009 аз ҷониби Колин Персивал ҳамчун намоиши функсияи ҳосилаи калиди скрипт навишта шудааст. Он дар бисёре аз тақсимоти Linux ва BSD дастрас мебошад.

Ҳамчунин бингаред

• Argon2 - ғолиби Озмуни Hashing Password дар 2015
• bcrypt - Функсияи парол-hashing дар асоси blowfish
• bcrypt - утилитаи рамзгузории файлҳои кросс-платформаи бар blowfish асосёфта, ки соли 2002 таҳия шудааст
• crypt - Функсияи китобхонаи Unix C
• crypt - утилитаи Unix
• ccrypt - утилита
• Функсияи ҳосилкунии калидӣ
• Дарозии калид
• mcrypt - утилита
• PBKDF2 - Функсияи истихроҷи калид дар асоси парол 2, ки ба таври васеъ истифода мешавад
• PufferFish - функсияи ҳашинг пароли кэш сахт дар асоси тарҳи беҳтар bcrypt
• Мубодилаи фазо ва вақт

Пайвандҳои беруна

• Саҳифаи scrypt дар вебсайти Tarsnap.
• Коғази аслии скрипт.
• scrypt