kryptografia-semestr-8/rsa.py

import sys
from hashlib import sha256, sha384
import os
import random

byteorder = sys.byteorder


def get_power_2_factors(n: int) -> (int, int):
    r = 0
    d = n
    while n > 0 and d % 2 == 0:
        d = d // 2
        r += 1
    return r, d


def miller_rabin_prime_test(n: int, k: int = 64) -> bool:
    # Factor powers of 2 from n - 1 s.t. n - 1 = 2^r * d
    r, d = get_power_2_factors(n - 1)

    for i in range(k):
        a = get_random_bits(n.bit_length())
        while a not in range(2, n - 2 + 1):
            a = get_random_bits(n.bit_length())
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        n_1_found = False
        for j in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                n_1_found = True
                break
        if not n_1_found:
            return False
    return True


def get_random_bits(bit_length: int) -> int:
    return int.from_bytes(os.urandom((bit_length + 7) // 8), 'big')


def bezpieczny_randint(poczatek_inkluzywny, koniec_ekskluzywny):
    dlugosc_przedzialu = koniec_ekskluzywny-poczatek_inkluzywny
    maksymalna_liczba_bitow_zapisu = dlugosc_przedzialu.bit_length()
    # liczba miedzy 0 a 2**maksymalna_liczba_bitow_zapisu
    wyn = get_random_bits(maksymalna_liczba_bitow_zapisu)
    # liczba miedzy 0 a dlugosc_przedzialu
    while wyn >= dlugosc_przedzialu:
        wyn = get_random_bits(maksymalna_liczba_bitow_zapisu)
    # liczba miedzy poczatek_inkluzywny a koniec_ekskluzywny
    wyn = poczatek_inkluzywny + wyn
    return wyn


def generate_prime_number(bit_length: int) -> int:
    # prime needs to be in range [2^(n-1), 2^n-1]
    low = pow(2, bit_length - 1)
    high = pow(2, bit_length) - 1

    while True:

        # Generate odd prime candidate in range
        candidate_prime = get_random_bits(bit_length)
        while candidate_prime not in range(low, high + 1) or not candidate_prime % 2:
            candidate_prime = get_random_bits(bit_length)

        # with k rounds, miller rabin test gives false positive with probability (1/4)^k = 1/(2^2k)
        k = 64
        if miller_rabin_prime_test(candidate_prime, k):
            return candidate_prime


def rozszerzony_algorytm_euklidesa(a0, b0):
    a, b = a0, b0
    x, y = 1, 0
    r, s = 0, 1
    while b != 0:
        c = a % b
        q = a // b
        a, b = b, c
        r_pom, s_pom = r, s
        r = x - q * r
        s = y - q * s
        x, y = r_pom, s_pom
    nwd = x * a0 + y * b0
    return a, x, y, nwd


def NWD(a, b):
    nwd1, _, _, nwd2 = rozszerzony_algorytm_euklidesa(a, b)
    if nwd1 == nwd2:
        return nwd1
    else:
        return None


def odwrotnosc_modulo(a, n):
    _, x, y, _ = rozszerzony_algorytm_euklidesa(a, n)
    if a != 1 and x == 1:
        odwrotnosc_a = "nie ma elementu odwrotnego"
    elif x > 0:
        odwrotnosc_a = x % n
    else:
        odwrotnosc_a = (n + x) % n
    return odwrotnosc_a


def szybkie_potegowanie_modulo(podstawa, wykladnik, rzad):
    pom = 1
    while wykladnik > 1:
        ostatni_bit = wykladnik & 1
        wykladnik >>= 1
        if ostatni_bit == 1:
            pom = (pom * podstawa) % rzad
        podstawa = (podstawa * podstawa) % rzad
    return (podstawa * pom) % rzad


def genRSA(n=2048):
    p = generate_prime_number(n)
    # print(p.bit_length())
    q = p
    while q == p:
        q = generate_prime_number(n)
    # print(q.bit_length())
    N = p * q
    fi_N = (p - 1) * (q - 1)
    print(N.bit_length(), fi_N.bit_length())
    e = bezpieczny_randint(2, fi_N)
    while NWD(e, fi_N) != 1:
        e = bezpieczny_randint(2, fi_N)
    d = odwrotnosc_modulo(e, fi_N)
    # print(e.bit_length(),d.bit_length())
    klucz_publiczny = (N, e)
    klucz_prywatny = d
    return klucz_publiczny, klucz_prywatny, p, q


def szyfrowanie_RSA_OAEP(N, e, m: bytes):
    byteorder = sys.byteorder
    # 256 + 128 = 384
    k = 256
    l = 128
    # G = sha384()
    # H = sha256()
    print("m", len(m) * 8)
    print("m", m)
    if len(m) * 8 != l:
        return "wiadomosc usi byc dlugosci l =" + str(l)
    m_prim = m.ljust(len(m) + k // 8, b"\0")
    int_m_prim = int.from_bytes(m_prim, byteorder)
    print("m'", len(m_prim) * 8)
    print("m'", m_prim)
    int_r = get_random_bits(k)
    r = int_r.to_bytes(k // 8, byteorder)
    print("r", len(r) * 8)
    print("r", r)
    int_G_od_r = int.from_bytes(sha384(r).digest(), byteorder)
    int_t = int_m_prim ^ int_G_od_r
    t = int_t.to_bytes((l + k) // 8, byteorder)
    print("t", len(t) * 8)
    print("t", t)
    int_H_od_t = int.from_bytes(sha256(t).digest(), byteorder)
    int_s = int_r ^ int_H_od_t
    s = int_s.to_bytes(k // 8, byteorder)
    print("s", len(s) * 8)
    print("s", s)
    m_prim_prim = s + t
    print("m''", len(m_prim_prim) * 8)
    print("m''", m_prim_prim)
    int_m_prim_prim = int.from_bytes(m_prim_prim, byteorder)
    c = szybkie_potegowanie_modulo(int_m_prim_prim, e, N)
    return c


def deszyfrowanie_RSA_OAEP(N, d, c):
    byteorder = sys.byteorder
    # 256 + 128 = 384
    k = 256
    l = 128
    # G = sha384()
    # H = sha256()
    int_m_prim_prim = szybkie_potegowanie_modulo(c, d, N)
    m_prim_prim = int_m_prim_prim.to_bytes((l + 2 * k) // 8, byteorder)
    print("m''", len(m_prim_prim) * 8)
    print("m''", m_prim_prim)
    t = m_prim_prim[-((l + k) // 8):]
    print("t", len(t) * 8)
    print("t", t)
    s = m_prim_prim[:(k // 8)]
    print("s", len(s) * 8)
    print("s", s)
    int_H_od_t = int.from_bytes(sha256(t).digest(), byteorder)
    int_s = int.from_bytes(s, byteorder)
    int_r = int_H_od_t ^ int_s
    r = int_r.to_bytes(k // 8, byteorder)
    print("r", len(r) * 8)
    print("r", r)
    int_G_od_r = int.from_bytes(sha384(r).digest(), byteorder)
    int_t = int.from_bytes(t, byteorder)
    int_m_prim = int_G_od_r ^ int_t
    m_prim = int_m_prim.to_bytes((l + k) // 8, byteorder)
    print("m'", len(m_prim) * 8)
    print("m'", m_prim)
    koncowki = m_prim[-(k // 8):]
    m = m_prim[:l // 8]
    if koncowki != b"\0".ljust(k // 8, b"\0"):
        print("kon")
        print(koncowki)
        print(b"\0".ljust(k // 8, b"\0"))
        print("cowki")
    return m


def efektywne_deszyfrowanie_RSA(N, d, c, p, q):
    u = odwrotnosc_modulo(p, q)
    c_p = c % p
    c_q = c % q
    d_p = d % (p - 1)
    d_q = d % (q - 1)
    m_p = szybkie_potegowanie_modulo(c_p, d_p, p)
    m_q = szybkie_potegowanie_modulo(c_q, d_q, q)
    m = (m_p + p * (m_q - m_p) * u) % N
    return m


def deszyfrowanie_RSA_OAEP_efektywne(N, d, c, p, q):
    byteorder = sys.byteorder
    # 256 + 128 = 384
    k = 256
    l = 128
    # G = sha384()
    # H = sha256()
    int_m_prim_prim = efektywne_deszyfrowanie_RSA(N, d, c, p, q)
    m_prim_prim = int_m_prim_prim.to_bytes((l + 2 * k) // 8, byteorder)
    print("m''", len(m_prim_prim) * 8)
    print("m''", m_prim_prim)
    t = m_prim_prim[-((l + k) // 8):]
    print("t", len(t) * 8)
    print("t", t)
    s = m_prim_prim[:(k // 8)]
    print("s", len(s) * 8)
    print("s", s)
    int_H_od_t = int.from_bytes(sha256(t).digest(), byteorder)
    int_s = int.from_bytes(s, byteorder)
    int_r = int_H_od_t ^ int_s
    r = int_r.to_bytes(k // 8, byteorder)
    print("r", len(r) * 8)
    print("r", r)
    int_G_od_r = int.from_bytes(sha384(r).digest(), byteorder)
    int_t = int.from_bytes(t, byteorder)
    int_m_prim = int_G_od_r ^ int_t
    m_prim = int_m_prim.to_bytes((l + k) // 8, byteorder)
    print("m'", len(m_prim) * 8)
    print("m'", m_prim)
    koncowki = m_prim[-(k // 8):]
    m = m_prim[:l // 8]
    if koncowki != b"\0".ljust(k // 8, b"\0"):
        print("kon")
        print(koncowki)
        print(b"\0".ljust(k // 8, b"\0"))
        print("cowki")
    return m


# klucz_publiczny_RSA, klucz_prywatny_RSA, p, q = (
#                                                     519761468615543605427347715703470532429938244355530617462517836775139947735532430649086044712389065327373881495341570956912263636228899450218205333731994709572385570226639327413165593530360209805759468603639857045256463923468775944877723831073218948735316969800684547536389344549931456857234306842372788643144370170015431494005792115059852604376019742040737720145831855341361995847454762357088678899180062704532000519408988445258760142165454104557986566507437171014234130588907895586535673103026294670410052684946543540355295153040713047596704353948168657913426604838668582082688505569615845354438639297748571125719945947883870935481915168118357450909437162890949276124288629273158626408730136153353280259385734094248099908877393332627830019602495378740189414275791739220123642063963148205857703085745460786497856110396863143452962185817050131451659771071779171468538379804253272573761890205034195675788656368202533040838395434243520115268109258521563259069746861504072033382067677548531381312853098367831348608517017347561078932501869038526817662345324458956129880592307734774686126383765519554521082281355928596367373896420049772278195723106268205519834478036673827492711851824231074849054234160240213942064673753130040021561496201,
#                                                     477381706395942701152074095578632486629565400458439476605265085853794121036702612260159616584121387309492215289565364823820329641787576027356541944084504070937525199582998228494161581256587963350479182569767709073476305942938578516914185238354982945951325610464183760057011556336116027667431478443971789852497566022190931964624926914512000465438808202901732238917670859079331357158287446481486109341772535642821404724625886765680916122532309926171425411343129633761470730490722435328973775404176016783739955436887938755254368532747248553601029668098763389748002919821495769996090735951060509426001668094204167013619340151559257016228800996225376949328480285921295583758343588892868414107256524587102802726669931221977934082695445776450539968355018778177567062955955188598370628274906129902341525667948146220455560650547385726862123568732001996709039776914328180353694837345124024464856436018138531057521237527151154874694659679915931307604482959674167927057989516514567590062270287113788435548631219164690228588947375243868674913030414096170014455884449983476702938473784682164922729359739421419438500787506002570332539986745630166359816334300274692876831789517660550946290972807224515579551609831535687760126827024718122063108706599), 351666562595755180375395684706241055066156015118305238714672681051882280187504041643434000791814441548607213636968471872699749514579264747751265631272256072725451071040601318567317130676266378472799425651993837557182657388293299120738132040687844779805705782033358582690112156036725659897429182523487027733035393136127607866012534194708593248355973043622949956480835065663676049584885243751590721741501965828757835520710448143589654198570646114663285241248290713467857410885600973553990582698560020712556891679552160547216847450959753723375562391525266281121596206287835239825464988412752920851291059488855778730214384761750487421888963628985845627716345194071713463878260961723623247223927256636464995367615914339908375807571549256908577125462826282135037163236879694999772105827399413764752262353954388137128091790174996148478228118409615917295349567618090677194660136786354642358341440475271809799562062575133857219513963659279640385931136925337147793582596685284559585465388622433797482322409875254412068070757284707921223037714540415540426945620781055610759002438036137835981012468827444588505213686787128969359012972104378460526475214473144375243797989638951510244270960646393807997876101642432170306423462852210882508497178399, 25135373776665590901202336545666836840803391456241601649197796217462555674052551470602221560430959564950903058760936416369952872220340695429584839910539112417172641186658957618681049568598438406515601629945861509808185343104246257658988353826830801833070838727357392230011787930325906736489581750024881433299826206439672753310114100220662748513681137812457302883579006216830084552049499018274245345348857361546260882853255668574117727827869922237413735566854945952091470823515266658679062817428979342500513620275531312300114575338687577827028450767856524439798014817991240510086446185465180093752648368250982692996851, 20678485756120477969749679171411892295363660397911095536909078058504743163718110463975943096121495385121226766215138672406087647843042984392942673880078680348165649479590165596137059916732118274875699928110613763860604584697412776630385407698849636163585027765534352995283408392656841447656433417025991247442767235071030016493820494123404672276837056547392384047230316759182798179296559194938230590081605300708541927122089496849298160531622588496007433560523950635471318918140715059942293286734964890852647775755004955456829006947025556582805868127595216838587483482482814544235364358121943295803510671636196385576851
# klucz_publiczny_RSA,klucz_prywatny_RSA, p, q = genRSA()
# print(klucz_publiczny_RSA, klucz_prywatny_RSA, p, q)
# N, e = klucz_publiczny_RSA
# d = klucz_prywatny_RSA
# m = "Thats my Kung Fu".encode("ASCII")
# c = szyfrowanie_RSA_OAEP(N, e, m)
# print("szyfrgr", c)
# m = deszyfrowanie_RSA_OAEP(N, d, c)
# print(m)
# m = deszyfrowanie_RSA_OAEP_efektywne(N, d, c, p, q)
# print(m)