Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Роберт МакЭлис әзірлеген асимметриялық шифрлау алгоритмі
Asymmetric encryption algorithm developed by Robert McEliece
Криптографияда МакЭлис криптожүйесі – 1978 жылы Роберт МакЭлис әзірлеген асимметриялық шифрлау алгоритмі. Бұл шифрлеу процесінде кездейсоқтық қолданудың алғашқы схемасы болды. Алгоритм криптографиялық қауымдастықта кеңінен қабылдануға ие болған жоқ, бірақ «посткванттық криптография» үшін үміткер болып табылады, өйткені ол Шор алгоритмін пайдаланатын шабуылдарға төтеп береді және жалпы алғанда Фурье дискретизациясы арқылы косеттік күйлерді өлшеуге қарсы тұрады. Алгоритмнің негізі – жалпы сызықтық кодты декодтаудың қиындығы (бұл NP-қиын екені белгілі). Жеке кілттің сипаттамасы үшін тиімді декодтау алгоритмі бар және қателерді түзете алатын қателерді түзетуші код таңдалады. Алғашқы алгоритм бинарлы Гоппа кодтарын пайдаланады (Паттерсонға тиесілі алгоритмнің арқасында оларды тиімді декодтауға болады). Ашық кілт жеке кілттен таңдалған кодты жалпы сызықтық код ретінде жасыру арқылы алынады. Осы үшін кодтың генераторлық матрицасы екі кездейсоқ таңдалған инвертирленетін матрицалармен өзгертіледі (төменде қараңыз). Бұл криптожүйенің әртүрлі код түрлерін қолданатын нұсқалары бар. Олардың көпшілігі аз қауіпті екені дәлелденді; олар құрылымдық декодтау арқылы бұзылды. МакЭлис Гоппа кодтарымен қазірге дейін криптоанализге қарсы тұрып келеді. Белгілі ең тиімді шабуылдар ақпараттық жиынтық декодтау алгоритмдерін қолданады. 2008 жылғы мақалада шабуыл және оны түзету туралы мәліметтер келтірілген. Тағы бір мақалада кванттық есептеулер үшін ақпараттық жиынтық декодтаудың жетілдірілуіне байланысты кілт өлшемдерін төрт есеге арттыру қажеттігі көрсетілген. МакЭлис криптожүйесінің, мысалы, RSA-ға қарағанда бірнеше артықшылықтары бар. Шифрлау және декодтау жылдам жүзеге асырылады. Ұзақ уақыт бойы МакЭлис қолтаңба жасау үшін қолданылмайды деп есептелді. Алайда, Niederreiter схемасы негізінде қолтаңба схемасын құруға болады, ол МакЭлис схемасының дуалды нұсқасы. МакЭлис криптожүйесінің басты кемшіліктерінің бірі – жеке және ашық кілттер үлкен матрицалар болып табылады. Стандартты параметрлерді таңдағанда ашық кілт 512 килобиттен тұрады.
In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling. The algorithm is based on the hardness of decoding a general linear code (which is known to be NP hard). For a description of the private key, an error correcting code is selected for which an efficient decoding algorithm is known, and which is able to correct errors. The original algorithm uses binary Goppa codes (subfield codes of algebraic geometry codes of a genus 0 curve over finite fields of characteristic 2); these codes can be efficiently decoded, thanks to an algorithm due to Patterson. The public key is derived from the private key by disguising the selected code as a general linear code. For this, the code's generator matrix is perturbated by two randomly selected invertible matrices and (see below). Variants of this cryptosystem exist, using different types of codes. Most of them were proven less secure; they were broken by structural decoding. McEliece with Goppa codes has resisted cryptanalysis so far. The most effective attacks known use information set decoding algorithms. A 2008 paper describes both an attack and a fix. Another paper shows that for quantum computing, key sizes must be increased by a factor of four due to improvements in information set decoding. The McEliece cryptosystem has some advantages over, for example, RSA. The encryption and decryption are faster. For a long time, it was thought that McEliece could not be used to produce signatures. However, a signature scheme can be constructed based on the Niederreiter scheme, the dual variant of the McEliece scheme. One of the main disadvantages of McEliece is that the private and public keys are large matrices. For a standard selection of parameters, the public key is 512 kilobits long.
Схеманың анықтамасы
МакЭлис үш алгоритмнен тұрады: қоғамдық және жеке кілтті құрайтын ықтималдық кілт жасау алгоритмі, ықтималдық шифрлау алгоритмі және детерминистік шифрлауды ашу алгоритмі. МакЭлис жүйесін пайдаланатын барлық қолданушылардың ортақ қауіпсіздік параметрлері болады: .
McEliece consists of three algorithms: a probabilistic key generation algorithm which produces a public and a private key, a probabilistic encryption algorithm, and a deterministic decryption algorithm. All users in a McEliece deployment share a set of common security parameters: .
Құрылымдық шабуылдар
Шабуылшы оның орнына "құрылымын" қалпына келтіруге тырысуы мүмкін, осылайша тиімді декодтау алгоритмін немесе басқа жеткілікті күшті, тиімді декодтау алгоритмін қалпына келтіреді. Кодтар тобының таңдауы шабуылдаушы үшін мұның мүмкін екендігін толықтай анықтайды. McEliece үшін көптеген кодтар отбасылары ұсынылды, және олардың көпшілігі Reed Solomon кодтары сияқты, тиімді декодтау алгоритмін қалпына келтіретін шабуылдар табылғандықтан толығымен "бұзылған". Бастапқыда ұсынылған бинарлы Goppa кодтары құрылымдық шабуылдарды жасау әрекеттеріне қарсы тұрған аз ғана кодтар отбасыларының бірі болып қала береді.
The attacker may instead attempt to recover the "structure" of , thereby recovering the efficient decoding algorithm or another sufficiently strong, efficient decoding algorithm. The family of codes from which is chosen completely determines whether this is possible for the attacker. Many code families have been proposed for McEliece, and most of them have been completely "broken" in the sense that attacks which recover an efficient decoding algorithm has been found, such as Reed Solomon codes. The originally proposed binary Goppa codes remain one of the few suggested families of codes which have largely resisted attempts at devising structural attacks.
Кванттық шифрлаудан кейінгі кандидат
Бұл алгоритмнің NTS KEM-мен үйлесімді нұсқасы NIST посткванттық шифрлау конкурсының үшінші кезеңінде қатысып, іріктелді.
A variant of this algorithm combined with NTS KEM was entered into and selected during the third round of the NIST post quantum encryption competition.