|
1. Írjunk programot, amely háromféle módszerrel meghatározza a multiplikatív inverzét mod b szerint. A három módszer a következő legyen:
- az összes érték kipróbálásának módszere
- a bináris kiterjesztett Eukleidészi algoritmus
- a kis-Fermat tételén (ha b prímszám), Euler tételén (tetszőleges b-re) alapuló algoritmus
2. Írjunk programot, mely affin módszerrel titkosít és visszafejt egy tetszőleges szövegállományt. A szövegállományon végezzünk elő-feldolgozást, oly módon hogy minden betűt alakítsunk nagybetűvé, és csak az angol ábécé betűit tartsuk meg, a többi karaktert vágjuk ki, majd az így kapott szöveg angol ábécé nagybetűinek feleltessük meg a megfelelő számkódokat (számkód tábla). A titkosítást a számkódokon végezzük.
3. Az alábbi titkosított szöveg, affin módszerrel volt rejtjelezve, ahol a titkosítást az angol ábécé 26 betűje felett végeztük, és az angol ábécé betűin kívül más írásjelet nem titkosítottunk. Határozzuk meg az eredeti szöveget és a kulcspárt, az összes lehetséges kulcs kipróbálásának módszerével.
EX GKLGTGWRGW BE HGDPGAODRG KIRZEX EKIH WIVERREW, RGK VEDRE E PEVOWTE. BGTEWDGIHYAX
4. Az alábbi két titkosított szöveg, affin módszerrel volt rejtjelezve, ahol a titkosítást az angol ábécé nagybetűi, a vessző, a pont és a szóköz felett végeztük, összesen M = 29 szimbólumot használva. A nagybetűknek a 0 és 26 közötti számkódokat, a vesszőnek a 26, a pontnak a 27, a szóköznek pedig a 28-as számkódot feleltettük meg. Egyéb írásjeleket nem tartalmazott az eredti fájl. Határozzuk meg mindkét esetben az eredeti szöveget és a rejtjelezéshez használt kulcsot, a következő módszerrel (ismert nyílt szövegű támadás / known plaintext attack):
5. Egy jpg kép Affin-256 módszerrel volt rejtjelezve, ahol a titkosítást a bájtok felett végeztük. Határozzuk meg az eredeti képet és a rejtjelezéshez használt kulcsot az összes kulcs kipróbálásának módszerével, tudva azt, hogy egy jpg első két bájtja 0xFF, 0xD8.
6. A jpg kép Affin-256 módszerrel volt rejtjelezve, ahol a titkosítást a bájtok felett végeztük. Határozzuk meg az eredeti képet tudva, hogy a rejtjelezéshez használt kulcs (a, b) = (113, 223). A megoldás során háromféleképpen is határozzuk meg a rejtjelezéshez használt a kulcs multiplikatív inverzét mod 256 szerint. A három módszer a következő legyen:
- az összes érték kipróbálásának módszere
- a bináris kiterjesztett Eukleidészi algoritmus
- Euler tételén alapuló algoritmus
7. A bmp kép Affin-256 módszerrel volt rejtjelezve, ahol a titkosítást a bájtok felett végeztük. Határozzuk meg rejtjelezéshez használt kulcsot, illetve az eredeti képet tudva, hogy 0xFF rejtjele 0x30, illetve 0x00 rejtjele 0x77 (ismert nyílt szövegű támadás / known plaintext attack).
C++, moduláris inverz meghatározása, kiterjesztett Eukleidészi algoritmus alkalmazása:
#include
using namespace std;
void extEuclid(int &d, int &x, int &y, int a, int b);
void mInv(int &x, int a, int b);
int main() {
int d, x, y;
int a = 9, b = 19;
extEuclid(d, x, y, a, b);
cout << d << " " << x << " " << y << endl;
cout << "ellenorzes: " << x * a + y * b << endl;
mInv(x, a, b);
if (x == -1)
cout << "nincs inverz" << endl;
else {
cout << "inverz: " << x << endl;
cout << "inverz ellenorzes: " << (a*x) % b << endl;
}
}
void mInv(int &x, int a, int b) {
int x0, x1;
int q, r, tb = b;
x0 = 1, x1 = 0;
while (true) {
q = a / b;
r = a - b * q;
if (r == 0) {
if (b!= 1) x = -1;
else x = (x1 + tb) % tb;
return;
}
x = x0 - q * x1;
x0 = x1, x1 = x;
a = b, b = r;
}
}
void extEuclid(int &d, int &x, int &y, int a, int b) {
int x0, x1, y0, y1;
int q, r;
x0 = 1, x1 = 0, y0 = 0, y1 = 1;
while (true) {
q = a / b;
r = a - b * q;
if (r == 0) {
d = b;
x = x1, y = y1;
return;
}
x = x0 - q * x1;
y = y0 - q * y1;
x0 = x1, x1 = x, y0 = y1, y1 = y;
a = b, b = r;
}
}
|