Elementarioji skaičių teorija kriptografijoje

Paprasta apgręžiama transformacija

Tarkime, kad mokomojo pavyzdžio pranešimas jau išreikštas vienu iš sveikųjų skaičių nuo 0 iki 7. Transformuokite x: padauginkite iš 3, pridėkite 1, tada palikite liekaną moduliu 8. Pranešimas 2 virsta 3·2+1 = 7. Norėdami jį atkurti, atimkite 1 ir vėl padauginkite iš 3: 3(7−1) = 18; šio skaičiaus liekana moduliu 8 yra 2.

Šis antrasis daugiklis tinka, nes 3·3 = 9 duoda liekaną 1 moduliu 8. Toliau pateiktas visas atvaizdis rodo, kuo virsta kiekvienas galimas pranešimas. Prieš atskleisdami atvirkštinės transformacijos skaičiavimą, numatykite, ar du skirtingi pranešimai gali virsti tuo pačiu užkoduotu skaičiumi.

Pasirengimas skaičiavimams ir trijų objektų atskyrimas

Sandaugoms, skirtumams su ženklu ir laipsniams su sveikaisiais rodikliais skaičiuoti naudokitės paskelbtomis pamokomis „Daugyba ir dalyba“, „Neigiamieji skaičiai ir absoliučioji vertė“ bei „Laipsniai, šaknys ir realiųjų skaičių tiesė“. Toliau kiekvienas reikalingas faktas apie pirminius skaičius, bendruosius daliklius ir kongruencijas apibrėžiamas ir įrodomas prieš jį taikant.

Atvirasis tekstas yra pradinis pranešimas. Šifruotasis tekstas yra transformuota jo išraiška. Raktas nurodo transformaciją arba jai atvirkštinę transformaciją. Čia pranešimai yra sveikieji skaičiai – reprezentantai iš nurodyto baigtinio intervalo. Norint žodį, failą ar baitų seką paversti tokiais skaičiais, reikia atskiro kodavimo; dviem skirtingiems tekstams negalima netyčia priskirti to paties reprezentanto.

Sveikųjų skaičių aibę žymėkime ℤ. Rašykime h | t, jei t = hk su sveikuoju skaičiumi k, o priešingu atveju – h ∤ t. Kai teigiamas modulis N ≥ 2, x ≡ y (mod N) reiškia N | (x−y). Kiekvienas sveikasis skaičius turi vieną kanoninę liekaną iš 0,…,N−1: dalykime su liekana šiame intervale. Kongruencija reiškia liekanų lygybę, o ne pradinių sveikųjų skaičių lygybę.

Skaitydami pirmą kartą, sekite apgręžiamą atvaizdį ir nedidelį RSA skaičiavimo pavyzdį, tada grįžkite prie sveikųjų skaičių tiesinės kombinacijos ir liekanų pirminiu moduliu įrodymų. Visą laiką turėkite omenyje sąlygą pranešimų sričiai ir skirtumą tarp pranešimo atkūrimo ir slaptumo.

Sveikųjų skaičių tiesinė kombinacija duoda atvirkštinį elementą

Kai a yra sveikasis skaičius ir N ≥ 2, gcd(a,N) yra didžiausias teigiamas sveikasis skaičius, dalijantis juos abu. Tokių daliklių yra, o jų sąrašas baigtinis, nes jie dalija N. Skaičiai yra tarpusavyje pirminiai, kai šis didžiausias bendrasis daliklis yra 1. Skaičiaus a atvirkštinis elementas moduliu N yra sveikasis skaičius u, tenkinantis au ≡ 1 (mod N).

Dalyba su liekana leidžia užrašyti A = qB+r, kai A yra neneigiamas, B – teigiamas ir 0 ≤ r < B. Bendrasis A,B daliklis dalija B,r, nes r gaunamas atėmus qB; bendrasis B,r daliklis dalija A, nes A gaunamas pridėjus qB. Kartojant (A,B) → (B,r), bendrieji dalikliai išlieka, o teigiamos liekanos griežtai mažėja, kol viena tampa lygi nuliui. Paskutinė nenulinė reikšmė yra didžiausias bendrasis daliklis.

Pradėkime nuo N = 0·a+1·N ir |a| = s·a+0·N, kur s yra 1, kai a ≥ 0, ir −1, kai a < 0. Kiekviena nauja liekana yra dviejų tiesinių kombinacijų su sveikaisiais koeficientais skirtumas, todėl galutinis didžiausias bendrasis daliklis yra ua+vN su sveikaisiais koeficientais. Kai a = 0, tapatybė yra N = 0·a+1·N. Taigi skaičiavimas duoda ir didžiausią bendrąjį daliklį, ir jo išraiškos tiesine kombinacija tapatybę.

Jei didžiausias bendrasis daliklis yra 1, iš ua+vN = 1 gauname au ≡ 1, taigi ir atvirkštinį elementą. Jei atvirkštinis elementas egzistuoja, au−1 yra N kartotinis, todėl kiekvienas bendrasis a,N daliklis dalija 1; didžiausias bendrasis daliklis turi būti 1. Taigi atvirkštinis elementas egzistuoja tada ir tik tada, kai daugiklis yra tarpusavyje pirminis su moduliu.

Jei gcd(a,N) = 1 ir N | at, padauginkime ua+vN = 1 iš t. Abu dešiniosios t = uat+vNt pusės nariai yra N kartotiniai, todėl N | t. Šis suprastinimo argumentas taip pat pagrįs toliau pateiktą liekanų pirminiu moduliu įrodymą. Sudėtis ir daugyba moduliu išsaugo kongruenciją, nes dalių skirtumų sumos ir xy−x′y′ = y(x−x′)+x′(y−y′) išlieka dalios iš N. Kartotinė daugyba duoda tą pačią taisyklę laipsniams su teigiamais sveikaisiais rodikliais.

Daugiklis lemia afininio atvaizdžio apgręžiamumą

Afininis liekanų atvaizdis yra y ≡ ax+b (mod N), kur a,b yra fiksuoti sveikieji skaičiai, o x – kanoninė liekana. Jei a turi atvirkštinį elementą u, dekodavimas pagal x ≡ u(y−b) atkuria įvestį: u(ax+b−b) ≡ x. Kiekvienas kanoninis šifrotekstas turi lygiai vieną kanoninį pirmavaizdį. Ir atvirkščiai, iš lygių išvesčių gauname a(x−x′) ≡ 0, todėl suprastinę gauname lygias kanonines įvestis.

Jei g = gcd(a,N) > 1, įvestys 0 ir N/g yra skirtingos kanoninės liekanos, kurių išvestis ta pati. Jų išvesčių skirtumas yra aN/g – skaičiaus N kartotinis, nes g dalija a. Tai įrodo, kad vienareikšmis dekodavimas neįmanomas su jokiu daugikliu, kuris nėra tarpusavyje pirminis su moduliu, o ne vien konkrečiame brėžinyje. Poslinkis b negali pašalinti kolizijos.

Kai a = 2,b = 1,N = 8, abu pranešimai 0 ir 4 užkoduojami kaip 1. Jokia funkcija, gaunanti tik šifrotekstą 1, negali grąžinti abiejų skirtingų pradinių pranešimų. Apgręžiamame pavyzdyje su a = 3 visos išvestys yra 1,4,7,2,5,0,3,6: kiekviena liekana pasirodo vieną kartą.

Vien grįžtamumas neužtikrina slaptumo. Stebėtojas, žinantis šį afininio šifro raktą, gali apskaičiuoti tą patį atvirkštinį atvaizdį; net ir nežinomą labai mažą raktą galima rasti išbandant visas galimybes. Šifras, kuris pasikartojančius simbolius apdoroja nepriklausomai, taip pat išsaugo jų pasikartojimo dėsningumus. Šie faktai taikomi nurodytam mokomajam atvaizdžiui, o ne reiškia teiginį, kad kiekvienas kriptografinis metodas yra afininis šifras.

Viešasis ir iššifravimo rodikliai atlieka skirtingus vaidmenis

Pasirinkite du skirtingus teigiamus pirminius skaičius p,q. Pirminis skaičius yra sveikasis skaičius, didesnis už 1, kurio vieninteliai teigiami dalikliai yra 1 ir jis pats. Pažymėkite N = pq ir T = (p−1)(q−1). Pasirinkite teigiamus sveikuosius skaičius e,d, kuriems ed ≡ 1 (mod T). Jei e ir T yra tarpusavyje pirminiai, toks d egzistuoja pagal sveikųjų skaičių tiesinio derinio tapatybę. Šios patogios rodiklių sąlygos pakanka mūsų atkūrimo įrodymui, tačiau tai nėra teiginys, kad šis iššifravimo rodiklis yra vienintelis galimas. T yra dviejų vienetu sumažintų pirminių skaičių sandauga; toliau pateiktas įrodymas paaiškina, kodėl šis pasirinkimas tinka.

Aritmetinė šifravimo taisyklė kanoninį pranešimą m atvaizduoja į kanoninį šifruotą tekstą c ≡ m^e (mod N). Iššifravimas atvaizduoja c į r ≡ c^d (mod N). Viešoji pora yra (N,e); numatytasis gavėjas saugo iššifravimo rodiklį d. Mūsų mokomosiose lentelėse pateikiamos visos šios labai mažos reikšmės, kad būtų galima patikrinti matematinius skaičiavimus.

Imkime p = 3,q = 11. Tuomet N = 33,T = 20. Kai e = 3, dalydami su liekana pagal Euklido algoritmą gauname 20 = 6·3+2, 3 = 1·2+1 ir 2 = 2·1+0. Atlikę atgalinį įstatymą gauname 1 = 3−(20−6·3) = 7·3−20. Todėl d = 7 tinka ir ed = 21 = 1+20.

Pranešimas 7 užšifruojamas taip: 7³ = 343 = 10·33+13, taigi c = 13. Iššifruojant kėlimu septintuoju laipsniu atkuriamas 7, kaip rodo toliau pateiktas tikslus skaičiavimas. Šis vienas sėkmingas atvejis yra pavyzdys; vėlesnis įrodymas turi apimti ir visus kitus pranešimus, įskaitant 0 ir skaičių 3 arba 11 kartotinius.

Tarpinės liekanos turi būti mažos

Kartotinio kėlimo kvadratu metodas leidžia apskaičiuoti laipsnį prieš tai neužrašant milžiniško sveikojo skaičiaus, gaunamo keliant tuo laipsniu. Skaičiuojant 13^7 moduliu 33, 13² = 169 ≡ 4 ir 13⁴ ≡ 4² = 16. Kadangi 7 = 4+2+1, sudauginkite 16·4·13: pirmiausia 16·4 = 64 ≡ 31, paskui 31·13 = 403 ≡ 7. Kiekvieną pakeitimą liekana pagrindžia kongruencijų daugybos taisyklė.

Lentelėse pateikiami laipsniai su rodikliais 1,2,4,… ir nurodoma, kurie iš jų įtraukiami į sandaugą. Apskaičiuotas kartotinio kėlimo kvadratu rezultatas nebūtinai yra galutinės sandaugos daugiklis. Visi šios pamokos rodikliai yra teigiami, taip pat ir nulinio pranešimo atveju 0^e = 0. Nenaudojamas nei neapibrėžtas 0⁰, nei kėlimas neigiamu laipsniu.

Daugyba perstato nenulines liekanas pirminiu moduliu

Tegu p yra pirminis skaičius ir tarkime, kad p ∤ a. Jų didžiausias bendras daliklis yra 1, nes teigiamas bendras daliklis, dalijantis p, yra arba 1, arba p, o pastaroji galimybė atmesta. Padauginkite liekanas 1,2,…,p−1 iš a moduliu p. Nė viena netampa 0: suprastinus p | aj, gautume p | j, o tai neįmanoma, kai 1 ≤ j < p.

Jokie du rezultatai nesutampa. Jei aj ≡ ak, suprastinę gauname j ≡ k; iš jų kanoninių reikšmių intervalų išplaukia j = k. Yra p−1 skirtingų nenulinių rezultatų ir tik p−1 galimų nenulinių liekanų, todėl šie rezultatai yra būtent 1,2,…,p−1, išdėstyti tam tikra tvarka. Tai yra perstata: išdėstymas, kuriame kiekvienas elementas panaudojamas vieną kartą.

Tegu F = 1·2···(p−1) – sandauga, taip pat žymima (p−1)!. Kiekvienas daugiklis turi atvirkštinį elementą moduliu p, todėl jų atvirkštinių elementų sandauga yra F atvirkštinis elementas. Sudauginus gautas reikšmes, jų sandauga yra kongruenti a^(p−1)F ir kartu kongruenti F, nes ją sudaro tie patys daugikliai, tik kita tvarka. Padauginę iš F atvirkštinio elemento, gauname a^(p−1) ≡ 1 (mod p). Taip įrodoma mažoji Ferma teorema, laikantis būtinų sąlygų: modulis turi būti pirminis, o liekana – nenulinė.

Kai a = 3, p = 7, gaunamos reikšmės 3,6,2,5,1,4. Kiekviena nenulinė liekana pasirodo tiksliai vieną kartą, todėl 3⁶ ≡ 1 moduliu 7. Jei modulis sudėtinis, šios sąlygos gali būti netenkinamos: kai a = 2, N = 8, gaunama reikšmė 0, kitos reikšmės sutampa, o 2⁷ ≡ 0, o ne 1. Teorema neteigia, kad ši taisyklė su pirminį skaičių atitinkančiu laipsnio rodikliu galioja bet kokiam sudėtiniam moduliui.

Dalūs pranešimai ir patikrų pirminiais moduliais sujungimas

Kai p ir q yra skirtingi pirminiai skaičiai, o e ir d – teigiami sveikieji skaičiai, tenkinantys ed = 1+kT, T = (p−1)(q−1), sveikasis skaičius k yra neneigiamas, nes ed ≥ 1 ir T > 0. Iššifruotas pranešimas yra kongruentus (m^e)^d = m^(ed) moduliu N. Įrodysime m^(ed) ≡ m atskirai kiekvieno pirminio skaičiaus moduliu.

Skaičiuodami moduliu p, pirmiausia nagrinėkime atvejį p | m. Tiek m, tiek m^(ed) liekana yra 0, nes ed yra teigiamas. Kitu atveju pagal Ferma teoremą m^(p−1) ≡ 1. Kadangi ed = 1+k(q−1)(p−1), užrašykime m^(ed) = m·(m^(p−1))^(k(q−1)); šio reiškinio reikšmė kongruenti m. Jei paskutinis laipsnio rodiklis lygus nuliui, laipsnio pagrindas yra nenulinis, o laipsnio reikšmė lygi 1. Toks pat dviejų atvejų argumentas galioja moduliu q.

Norėdami sujungti patikras, pažymėkime D = m^(ed)−m. Žinome, kad p | D ir q | D. Užrašykime D = pt. Skirtingi pirminiai skaičiai p ir q yra tarpusavyje pirminiai, todėl iš q | pt, panaikinus daugiklį p, gauname q | t. Taigi pq | D, ir tai įrodo m^(ed) ≡ m (mod N). Vadinasi, dvi nepriklausomos patikros pirminiais moduliais nustato liekaną jų sandaugos moduliu.

Tiek pradinis pranešimas m, tiek atkurtas atstovas r priklauso aibei 0,…,N−1. Šiame intervale kongruencija reiškia lygybę, todėl r = m. Iš to išplaukia, kad šifravimas yra visų N kanoninių pranešimų perstata: vienodi šifrogramų duomenys būtų iššifruoti į vienodus pradinius pranešimus. Įrodymas apima abiejų pirminių skaičių kartotinius ir nulį, taip pat su moduliu tarpusavyje pirminius pranešimus.

Modelyje N = 33, e = 3, d = 7 pranešimas 3 dalijasi iš 3, bet vis tiek atkuriamas teisingai; pranešimui 11 taikomas nulinės liekanos atvejis moduliu 11, o pranešimui 0 – abu nulinės liekanos atvejai. Pilna lentelė patvirtina visus 33 konkrečius atvejus. Atkūrimą kiekvienai leistinai skirtingų pirminių skaičių porai pagrindžia bendrasis įrodymas, o ne vien ši baigtinė patikra.

Sutapimas ar vienas neatkurtas pranešimas atskleidžia netinkamą taisyklę

Kai N = 33 ir e = 2, abu pranešimai 1 ir 32 užšifruojami į 1, nes 32 ≡ −1 ir (−1)² = 1. Čia gcd(2,20) = 2, todėl atvirkštinis laipsnio rodiklis moduliu 20 neegzistuoja. Joks iššifravimo algoritmas, naudojantis vien šią šifrogramą, negali atkurti abiejų pradinių pranešimų.

Palikę e = 3, bet pasirinkę d = 3, gauname ed = 9, kuris nėra kongruentus 1 moduliu 20. Pranešimas 7 užšifruojamas į 13, tačiau siūlomas iššifravimo algoritmas duoda 13³ = 2197 ≡ 19 moduliu 33. Kai kurie pranešimai, pavyzdžiui, 0 ar 1, vis tiek atkuriami; šie sėkmingi atvejai nepagrindžia visų pranešimų atkūrimo.

Suformuluotai teoremai taip pat būtina, kad pirminiai skaičiai būtų skirtingi. Jei p = q = 3, N = 9, o pagal tą pačią formulę apskaičiuota sandauga T = (3−1)² = 4, pasirinkus e = 5, d = 1 gaunama ed ≡ 1 šio T moduliu. Tačiau pranešimas 3 užšifruojamas į 3⁵ ≡ 0 moduliu 9 ir iššifruojamas į 0. Dvi patikros moduliu 3 negali reikšti dalumo iš 9. Šis pavyzdys sąmoningai neatitinka rakto apibrėžimo, reikalaujančio skirtingų pirminių skaičių.

Atkūrimo įrodymas atsako į vieną klausimą apie sistemą

Įrodymas, apimantis visus pranešimus, patvirtina teisingumą: numatyta iššifravimo taisyklė apverčia aritmetinį atvaizdį. Jis neįrodo, kad stebėtojas negali atkurti pranešimo. Žinant p ir q, galima rasti T, o tada, taikant Euklido dalybą, ir d. Išskaidyti 33 dauginamaisiais nesunku, todėl šis konkretus viešojo rakto pavyzdys nieko neslepia nuo žmogaus, kuris išnagrinėja jo mažytę lentelę.

Vien kėlimas laipsniu yra deterministinis: naudojant tą patį raktą, vienodi pranešimų atstovai duoda vienodus šifrogramų tekstus. Jei žinoma pranešimų aibė yra maža, stebėtojas gali viešuoju raktu užšifruoti kiekvieną galimą pranešimą ir palyginti rezultatą su perimtu šifrogramos tekstu. Šioje lentelėje kaip tik pateiktas toks išsamus palyginimas.

Jis taip pat išsaugo atstovų daugybą. Jei c₁ ≡ m₁^e ir c₂ ≡ m₂^e, tai c₁c₂ ≡ (m₁m₂)^e moduliu N. Naudojant mūsų raktą, 2 užšifruojamas į 8, o 3 – į 27. Jų šifrogramų tekstų sandaugos 216 liekana yra 18, kuri taip pat yra 6 šifravimo rezultatas. Ši naudinga aritmetinė tapatybė negarantuoja pranešimo vientisumo.

Tikrosios RSA šifravimo schemos kėlimo laipsniu primityvą derina su nustatytu pranešimų kodavimu ir užpildymu. Pavyzdžiui, RSAES-OAEP kodavime naudojama atsitiktinė pradinė reikšmė. Šioje pamokoje neįgyvendinama nei ši schema, nei skaitmeninio parašo protokolas. Vien didesni skaičiai nepaverstų jos paprastų liekanų atvaizdžių visaverte saugia sistema.

Numatykite apverčiamumą, tada patikrinkite kiekvieną eilutę

Palyginkite afininio atvaizdžio koliziją su apverčiamu afininiu atvaizdžiu, tada išnagrinėkite taisyklingą RSA aritmetiką, neteisingą privatųjį eksponentą, lyginį viešąjį eksponentą ir kontrpavyzdį su pasikartojančiu pirminiu daugikliu. Numatykite, ar pasirinktas pranešimas bus atkurtas ir ar šis rezultatas galioja kiekvienam lentelės pranešimui.

Pavyzdyje su pirminiu skaičiumi numatykite, ar dauginant galima gauti nulį arba tą patį rezultatą pakartotinai. Prie kiekvieno pateikto atvaizdžio išvardyta visa jo baigtinė apibrėžimo sritis; formulės ir įrodymai tiksliai nusako, kurios išvados galioja ir už šių atvejų ribų.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Užšifruokite pranešimą 5 pagal y ≡ 3x+1 (mod 8), tada iššifruokite rezultatą.

   Rodyti atsakymą ir paaiškinimą

   Pranešimas 5 užšifruojamas į 0, o iššifravus gaunama 3(0−1) ≡ 5 moduliu 8.

   3·5+1 = 16 liekana yra 0. Neigiamo skaičiaus −3 kanoninė liekana yra 5, todėl nulinis šifrotekstas nebūtinai reiškia, kad pradinis pranešimas buvo nulis.

2. Kai y ≡ 2x+5 (mod 8), pateikite du skirtingus pranešimus, kurių šifrotekstas vienodas.

   Rodyti atsakymą ir paaiškinimą

   Abu pranešimai 0 ir 4 užšifruojami į 5.

   Antrasis sveikasis išvesties skaičius yra 2·4+5 = 13 ≡ 5. Pakeitus poslinkį, skirtumas 8 tarp šių išvesties skaičių išlieka.

3. Paaiškinkite, kodėl lygybė 1 = 7·3−20 duoda d = 7 pavyzdyje, kuriame N = 33, e = 3.

   Rodyti atsakymą ir paaiškinimą

   Iš jos gauname 3·7 ≡ 1 moduliu 20, kur 20 = (3−1)(11−1).

   Reikiamas atvirkštinis elementas imamas moduliu, lygiu vienetu sumažintų pirminių skaičių sandaugai, o ne moduliu 33. Ši lygybė taip pat patvirtina, kad 3 ir 20 yra tarpusavyje pirminiai.

4. Apskaičiuokite pranešimo 11 šifrogramą, kai e = 3, N = 33. Ar jam taikomas visiems pranešimams skirtas įrodymas?

   Rodyti atsakymą ir paaiškinimą

   Pranešimas 11 užšifruojamas į 11, o iššifravus atkuriamas 11. Taip, įrodymas apima ir šį pranešimą.

   11³ = 1331 = 40·33+11. Moduliu 11 taikomas nulinės liekanos atvejis, o moduliu 3 – nenulinės liekanos atvejis. Bendras daliklis su N nereiškia, kad pranešimui įrodymas netaikomas.

5. Ar remiantis pateikta teorema apie pirminius skaičius galima daryti išvadą, kad 2⁷ ≡ 1 moduliu 8? Kokia yra tikroji šio laipsnio liekana?

   Rodyti atsakymą ir paaiškinimą

   Ne: 8 yra sudėtinis skaičius, o 2⁷ ≡ 0 moduliu 8.

   Teorema reikalauja, kad modulis būtų pirminis skaičius, o daugiklis nesidalytų iš to pirminio skaičiaus. Pakeisti p bet kuriuo teigiamu sveikuoju skaičiumi nepagrįsta.

6. Kodėl įrodyme moduliu, lygiu pirminiam skaičiui p, galima suprastinti iš F = 1·2···(p−1)?

   Rodyti atsakymą ir paaiškinimą

   Kiekvieno daugiklio liekana moduliu p yra nenulinė ir kiekvienas daugiklis turi atvirkštinį elementą; šių atvirkštinių elementų sandauga yra F atvirkštinis elementas.

   Nė vienas dauginamasis nesidalija iš p. Suprastinimas yra daugyba iš egzistuojančio atvirkštinio elemento, o ne įprasta dalyba iš liekanos be jokios sąlygos.

7. Kai N = 33, e = 3, d = 3, pranešimas 7 užšifruojamas į 13. Ką grąžina siūlomas iššifravimo algoritmas?

   Rodyti atsakymą ir paaiškinimą

   Jis grąžina 19, todėl pranešimas neatkuriamas.

   13³ = 2197 = 66·33+19. Čia ed = 9 nėra kongruentus 1 moduliu 20; teisingas kai kurių kitų pranešimų atkūrimas nėra įrodymas, kad atkuriami visi pranešimai.

8. Jei skirtingi pirminiai skaičiai p ir q abu dalija D, kodėl pq dalija D?

   Rodyti atsakymą ir paaiškinimą

   Užrašykime D = pt. Kadangi q dalija pt, o p ir q yra tarpusavyje pirminiai, suprastinę gauname q | t, taigi D yra pq kartotinis.

   Reikiamą žingsnį pagrindžia suprastinimo įrodymas, naudojantis tiesinį derinį su sveikaisiais koeficientais. Pakartojus tą patį pirminį skaičių, tarpusavio pirminumo sąlyga nebūtų tenkinama.

9. Jei prieš šifruodami, to nenurodę, pradinius sveikuosius skaičius 7 ir 40 pakeičiate jų liekanomis moduliu 33, ar iššifravimo algoritmas gali juos atskirti?

   Rodyti atsakymą ir paaiškinimą

   Ne. Abu pakeičiami tuo pačiu kanoniniu atstovu 7, todėl jų šifrograma vienoda.

   Teiginys apie visų pranešimų atkūrimą taikomas nurodytam įvesties diapazonui 0,…,32. Atskiras kodavimas turi išsaugoti informaciją apie ilgesnius arba į šį diapazoną nepatenkančius pradinius pranešimus.

10. Stebėtojas žino, kad pranešimas yra vienas iš 0,…,32, ir žino viešąjį raktą (33,3). Ar atkūrimo įrodymas užkerta kelią palyginimui su galimų pranešimų lentele?

    Rodyti atsakymą ir paaiškinimą

    Ne. Stebėtojas gali užšifruoti visus 33 galimus pranešimus ir palyginti jų šifrogramas.

    Su šiuo leistinu aritmetiniu raktu atvaizdis yra permutacija, todėl kiekvienas atitinkamas šifrotekstas nurodo vieną kandidatą. Teisingumas ir slaptumas yra skirtingi teiginiai.

11. Pranešimai 2 ir 3 užšifruojami į 8 ir 27, kai N = 33, e = 3. Palyginkite šifrotekstų sandaugą su 6 užšifravimo rezultatu.

    Rodyti atsakymą ir paaiškinimą

    8·27 ≡ 18 moduliu 33, o 6³ ≡ 18 moduliu 33.

    Kėlimas laipsniu išsaugo atstovų daugybą. Ši tapatybė yra paties kriptografinio primityvo savybė, o ne autentiškumo ar vientisumo įrodymas.

Ką verta įsidėmėti

• Kad aritmetinis šifravimas leistų atkurti pradinį pranešimą, pirmiausia reikia apibrėžti sveikaskaičių pranešimų sritį ir grįžtamąjį jų vaizdavimą.
• Afininis atvaizdis yra grįžtamasis tada ir tik tada, kai jo daugiklis ir modulis yra tarpusavyje pirminiai; poslinkis negali pašalinti kolizijų.
• Tiesinės kombinacijos su sveikaisiais koeficientais leidžia rasti atvirkštinius elementus moduliu ir pagrįstai suprastinti.
• Daugyba pirminio skaičiaus moduliu permutuoja visas nenulines liekanas ir taip įrodo teoremą apie laipsnį pirminio skaičiaus moduliu, laikantis jos sąlygų.
• RSA aritmetika su skirtingais pirminiais skaičiais, kai ed ≡ 1 moduliu (p−1)(q−1), atkuria kiekvieną kanoninį pranešimą, įskaitant nulį ir pranešimus, kurie nėra tarpusavyje pirminiai su moduliu.
• Kartotinis kėlimas kvadratu išsaugo tikslias liekanas neskaičiuojant milžiniškų įprastų laipsnių.
• Vien teisingas atkūrimas, dideli skaičiai ir pats kėlimas laipsniu neužtikrina šifravimo schemos saugumo.