Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Криптографияда қарсыластың артықшылығы – криптографиялық алгоритмге шабуыл жасаудың қаншалықты сәтті екенін өлшеудің бір жолы, оны сол типтегі алгоритмнің идеалданған нұсқасынан ажырату арқылы. Бұл контексте "қарсылас" – адам емес, алгоритм екенін ескеріңіз. Криптографиялық алгоритм, егер қарсыластың есептеу ресурстарының белгіленген шектеріне байланысты, қарсыластың нақты емес артықшылығы болмаса, қауіпті деп есептеледі (нақты қауіпсіздікке қараңыз). "Нақты емес" әдетте "O(2−p)" ішінде дегенді білдіреді, мұнда p – алгоритммен байланысты қауіпсіздік параметрі. Мысалы, p – блок шифры кілтіндегі биттер саны болуы мүмкін.
In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm. Note that in this context, the "adversary" is itself an algorithm and not a person. A cryptographic algorithm is considered secure if no adversary has a non negligible advantage, subject to specified bounds on the adversary's computational resources (see concrete security). "Negligible" usually means "within O(2−p)" where p is a security parameter associated with the algorithm. For example, p might be the number of bits in a block cipher's key.
Тұжырымдаманың сипаттамасы
F зерттеліп жатқан функцияның оракулы болсын, ал G сол типтегі идеалданған функцияның оракулы болсын. Қарсылас A – F немесе G кіріс ретінде берілген, 1 немесе 0 шығаратын ықтималдық алгоритмі. А-ның міндеті – берілген оракулға сұрақтар жолдау арқылы F пен G арасын ажырату. Біз былай айтамыз:
Let F be an oracle for the function being studied, and let G be an oracle for an idealized function of that type. The adversary A is a probabilistic algorithm, given F or G as input, and which outputs 1 or 0. A's job is to distinguish F from G, based on making queries to the oracle that it's given. We say:
Мысалдар
F DES блоктық шифрінің кездейсоқ мысалы болсын. Бұл шифр 64 биттік блоктардан және 56 биттік кілттен тұрады. Сондықтан кілт 264 мүмкін 64 биттік блоктардың 256 мүмкін орналасуының бірін таңдайды. "Кездейсоқ DES мысалы" дегеніміз, біздің F оракулымыз DES-ті K кілтін (жау үшін белгісіз) пайдаланып есептейді, мұнда K 256 мүмкін кілттердің арасынан тең ықтималдықпен таңдалады. Біз DES мысалын идеалдандырылған 64 биттік блок шифрімен салыстырғымыз келеді, яғни 64 биттік блоктардың (264)! мүмкін орналасуларынан кездейсоқ таңдалған орналасу. Бұл кездейсоқ таңдалған орналасуды G деп атайық. Стирлинг жуықтауынан (264)! шамамен тең екенін ескеріңіз, сондықтан қандай орналасу таңдалғанын анықтау үшін нақты компьютерде дәл көрсетуге тым үлкен санды жазу қажет. Басқаша айтқанда, G – бұл "шифр" мысалы, оның "кілт ұзындығы" шамамен 1021 бит, бұл да компьютерде сақтау үшін тым үлкен. (Бірақ біз кездейсоқ оракул қолданып, сұраулар санына пропорционал сақтау кеңістігімен G-ді іске асыра аламыз). Бізге берілген оракулдар кез келген таңдалған мәтінді шифрлайтындықтан, біз таңдалған мәтіндік шабуылды немесе CPA модельдейміз, ал біз есептеген артықшылықты аталған қарсыластың CPA артықшылығы деп атауға болады. Егер бізде шифрлау оракулдары да болса, біз таңдалған шифрмәтіндік шабуылды немесе CCA-ны жасап, қарсыластың CCA артықшылығын табатын болар едік.
Let F be a random instance of the DES block cipher. This cipher has 64 bit blocks and a 56 bit key. The key therefore selects one of a family of 256 permutations on the 264 possible 64 bit blocks. A "random DES instance" means our oracle F computes DES using some key K (which is unknown to the adversary) where K is selected from the 256 possible keys with equal probability. We want to compare the DES instance with an idealized 64 bit block cipher, meaning a permutation selected at random from the (264)! possible permutations on 64 bit blocks. Call this randomly selected permutation G. Note from Stirling's approximation that (264)! is around , so even specifying which permutation is selected requires writing down a number too large to represent exactly in any real computer. Viewed another way, G is an instance of a "cipher" whose "key length" is about 1021 bits, which again is too large to fit in a computer. (We can, however, implement G with storage space proportional to the number of queries, using a random oracle). Note that because the oracles we're given encrypt any plaintext of our choosing, we're modelling a chosen plaintext attack or CPA, and the advantage we're calculating can be called the CPA advantage of a given adversary. If we also had decryption oracles available, we'd be doing a chosen ciphertext attack or CCA and finding the CCA advantage of the adversary.
1-ші мысал: Кездейсоқ болжау
Осы қарсыласты А0 деп атаңыз. Ол жай ғана тиықты лақтырып, тең ықтималдықпен 1 немесе 0 қайтарады, ал оракулға сұрау жасамайды. Сондықтан, Pr[A0(F)=1] және Pr[A0(G)=1] екеуі де 0,5-ке тең. Бұл ықтималдықтардың айырмашылығы нөл болғандықтан, Adv(A0) нөлге тең. Егер біз әрқашан 0 немесе әрқашан 1 қайтаратын болсақ, F және G үшін ықтималдық бірдей болады, демек, артықшылық нөл. Бұл қарсылас F пен G-ді ажырата алмайды. Егер біз шифр жасаушылар болсақ, біздің тілегіміз (әлдеқайда қиынға соғуы мүмкін) – кез келген қарсыластың осыдан едәуір жақсы нәтиже көрсетуіне есептеу жүзінде мүмкіндік бермеу. Егер біз күшпен іздеуден жылдам болатын айырмашылықты таба алмайтын шифр құра алсақ, онда біз сәттілікке жеткен болар едік.
Call this adversary A0. It simply flips a coin and returns 1 or 0 with equal probability and without making any oracle calls. Thus, Pr[A0(F)=1] and Pr[A0(G)=1] are both 0.5. The difference between these probabilities is zero, so Adv(A0) is zero. The same thing applies if we always return 0, or always return 1: the probability is the same for both F and G, so the advantage is zero. This adversary can't tell F and G apart. If we're cipher designers, our desire (maybe not achievable) is to make it so that it's computationally infeasible for any adversary to do significantly better than this. We will have succeeded if we can make a cipher for which there's no distinguisher faster than brute force search.