Vissza

9. labor
I.
  1. Az állományban számpárok vannak: a, m egész számok. Olvassuk ki rendre ezeket a számokat és ha van megoldás, akkor a kiterjesztett Eukleidészi algoritmus segítségével oldjuk meg a következő lineáris kongruenciát:a·x = 1 mod m, azaz határozzuk meg az a szám inverzét mod m szerint.
  2. Az állományban számhármasok vannak: a, m, b egész számok. Olvassuk ki rendre ezeket a számokat és ha van megoldás, a kiterjesztett Eukleidészi algoritmus segítségével, minden számhármasra, határozzuk meg az alábbi lineáris kongruencia megoldásait: a·x = b mod m. Ha több mint 10 megoldás van, akkor az eredményt írjuk fileba.
  3. Az állományban számpárok vannak: a, m egész számok. Olvassuk ki rendre ezeket a számokat, és ha az m prímszám, a kis Fermat tétel segítségével, minden számpárra, oldjuk meg az alábbi lineáris kongruenciát: a·x = 1 mod m, azaz határozzuk meg az a szám inverzét mod m szerint.
  4. Az állományban számhármasok vannak: a, m, b egész számok. Olvassuk ki rendre ezeket a számokat és ha az m prímszám, akkor a kis Fermat tétel segítségével, minden számhármasra, oldjuk meg az alábbi lineáris kongruenciát: a·x = b mod m.
  5. Hasonlítsuk össze a brute-force, a kiterjesztett eukleidész algoritmus és az Euler-tételen alapuló modulásri inverz értéket meghatározó algoritmus futási idejét.
  6. Határozzuk meg egy adott n szám prímtényezős felbontását.
  7. Határozzuk meg n! prímtényezős felbontását.
  8. Adott x szám esetében, határozzuk meg az Euler függvény értékét.
II.
    A lenti linkeken egy kliens-szerver alkalmazásban a szerver a beolvasott p, q prímszámok alapján meghatározza az n, e, d értékeket, majd az n, e értékeket átküldi a kliensnek. A kliens véletlenszerűen generál egy K értéket, titkosítja és a titkosított értéket visszaküldi a szervernek. Próbáljuk ki az alkalmazást a követlező p, q értékekre:
    p = 57221
    q = 50539

    p = 260164765355227110949609066512020267767
    q = 328707870425789712203825533734495450589

    Az alkalmazást írjuk úgy át, hogy szerver oldalon, külön menüpontban, kulcsgenerálás néven lehessen meghatározni a p, q, e, d, n értékeket, illetve lelehessen menteni őket egy-egy fileba, külön fileba a publikus kulcs base64-es alakját, külön a privát kulcs base64-es alakját. A p, q értékek legalább 512 bites prímek kell legyenek. A kulcscserét módosítsuk úgy, hogy lehetőség legyen a fileba lementett kulcsokat kiolvasni és azokkal dolgozni.

    Szerver-kód, kliens-kód