Hvordan kan en affin chiffer være injektiv?

/ / Udgivet i Cybersecurity, Grundlæggende om EITC/IS/CCF klassisk kryptografi, Kryptografiens historie, Modulære aritmetiske og historiske koder

En affin chiffer er en type monoalfabetisk substitutionsciffer, der bruger matematiske funktioner til at kryptere og dekryptere meddelelser. Specifikt bruger krypteringsfunktionen af ​​en affin chiffer en lineær transformation af formen:

    \[ E(x) = (ax + b) \mod m \]

hvor:
- x er den numeriske ækvivalent til bogstavet i almindelig tekst.
- a og b er konstanter, der tjener som nøglen til chifferen.
- m er størrelsen af ​​alfabetet (f.eks. m = 26 for det engelske alfabet).

For at den affine chiffer skal være injektiv, hvilket betyder, at hvert input er knyttet til et unikt output (dvs. det er en en-til-en funktion), nøglekomponenten a skal have en bestemt egenskab. Denne egenskab er det a skal være coprime med m. To tal er coprime, hvis deres største fælles divisor (GCD) er 1.

Injektivitet og Coprimality

At forstå hvorfor a skal være coprime med m for at den affine chiffer skal være injektiv, skal du overveje implikationerne af krypteringsfunktionen:

    \[ E(x) = (ax + b) \mod m \]

If a og m ikke er coprime, så findes der heltal k og l sådan at:

    \[ \gcd(a, m) = d > 1 \]

Dette betyder, at a og m deler en fælles faktor d. Følgelig ville der være flere værdier af x det, når ganget med a og reduceret modulo m, kunne give det samme resultat. Dette er i strid med injektivitetskravet, fordi forskellige bogstaver i almindelig tekst vil knyttes til det samme chiffertekstbogstav.

Eksempel på ikke-injektivitet

Overvej et alfabet af størrelse m = 26 Og vælg a = 13 og b = 5. Krypteringsfunktionen bliver:

    \[ E(x) = (13x + 5) \mod 26 \]

Siden \gcd(13, 26) = 13 \neq 1, a og m er ikke coprime. Lad os undersøge kortlægningen for x = 0 og x = 2:

Til x = 0:

    \[ E(0) = (13 \cdot 0 + 5) \mod 26 = 5 \]

Til x = 2:

    \[ E(2) = (13 \cdot 2 + 5) \mod 26 = (26 + 5) \mod 26 = 5 \]

Både x = 0 og x = 2 kort til det samme chiffertekst bogstav, 5, der viser ikke-injektivitet.

Sikring af injektivitet

For at sikre, at den affine chiffer er injektiv, a skal vælges sådan \gcd(a, m) = 1. Dette garanterer det a har en multiplikativ invers modulo m, hvilket er vigtigt for at dekryptere beskeden. Dekrypteringsfunktionen er givet af:

    \[ D(y) = a^{-1}(y - b) \mod m \]

hvor a^{-1} er den multiplikative inverse af a modulo m. Den multiplikative inverse a^{-1} eksisterer hvis og kun hvis \gcd(a, m) = 1.

Eksempel på Injektivitet

Overvej igen et alfabet af størrelse m = 26, men denne gang vælge a = 7 og b = 3. Krypteringsfunktionen er:

    \[ E(x) = (7x + 3) \mod 26 \]

Siden \gcd(7, 26) = 1, a og m er coprime, hvilket sikrer injektivitet. Lad os undersøge kortlægningen for x = 0 og x = 2:

Til x = 0:

    \[ E(0) = (7 \cdot 0 + 3) \mod 26 = 3 \]

Til x = 2:

    \[ E(2) = (7 \cdot 2 + 3) \mod 26 = (14 + 3) \mod 26 = 17 \]

Her, x = 0 kort til 3 og x = 2 kort til 17, hvilket demonstrerer, at forskellige almindelige bogstaver knytter sig til forskellige chiffertekstbogstaver og dermed opretholder injektiviteten.

Dekryptering med injektivitet

Givet krypteringsfunktionen E(x) = (7x + 3) \mod 26, skal vi finde den multiplikative inverse af 7 modulo 26 for at dekryptere beskeden. Den multiplikative inverse a^{-1} tilfredsstiller:

    \[ 7a^{-1} \equiv 1 \mod 26 \]

Ved at bruge den udvidede euklidiske algoritme finder vi, at den multiplikative inverse af 7 modulo 26 er 15, fordi:

    \[ 7 \cdot 15 \mod 26 = 105 \mod 26 = 1 \]

Således er dekrypteringsfunktionen:

    \[ D(y) = 15(y - 3) \mod 26 \]

Lad os dekryptere chifferteksten bogstav 17:

    \[ D(17) = 15(17 - 3) \mod 26 = 15 \cdot 14 \mod 26 = 210 \mod 26 = 2 \]

Dette viser, at dekrypteringsprocessen gendanner det originale almindelige tekstbrev korrekt.

En affin chiffer kan være injektiv, hvis og kun hvis konstanten a brugt i krypteringsfunktionen er coprime med størrelsen af ​​alfabetet m. Dette sikrer en en-til-en-mapping mellem almindelig tekst og chiffertekstbogstaver, hvilket gør chifferen både sikker og reversibel. Injektiviteten af ​​den affine cipher er vigtig for at bevare integriteten af ​​den krypterede meddelelse og sikre, at hvert almindeligt tekstbogstav afbildes til et unikt chiffertekstbogstav og omvendt.

Andre seneste spørgsmål og svar vedr Grundlæggende om EITC/IS/CCF klassisk kryptografi:

Se flere spørgsmål og svar i EITC/IS/CCF Classical Cryptography Fundamentals

Flere spørgsmål og svar:

Tagged under: , , , , ,