Another encryption script. This closely resembles the Paillier cryptosystem.

from Crypto.Util.number import getStrongPrime
from math import gcd
from random import randint
from typing import Tuple
from Crypto.Cipher import AES
from hashlib import sha256

flag = b"PWNME{xxxxxxxxxxxxxxxxxxxxxxxxx}"

def generate_primes() -> int:
    p = getStrongPrime(512)
    q = getStrongPrime(512)

    while gcd(p*q, (p-1)*(q-1)) != 1:
        p = getStrongPrime(512)
        q = getStrongPrime(512)

    return p*q

def generate_public_key() -> Tuple[int, int]:
    n = generate_primes()
    k = randint(2, n-1)
    while gcd(k, n) != 1:
        k = randint(2, n-1)
    g = 1 + k * n
    return n, g, k

n, g, k = generate_public_key()

a = randint(2, n-1)
b = randint(2, n-1)

A = pow(g, a, n*n)
B = pow(g, b, n*n)

secret_key = pow(B, a, n*n)

def encrypt(m: bytes, secret_key: int) -> str:
    hash_secret_key = sha256(str(secret_key).encode()).digest()
    cipher = AES.new(hash_secret_key, AES.MODE_ECB)
    return cipher.encrypt(m).hex()

print(f"{n = }")
print(f"{g = }")
print(f"{k = }")

print(f"{A = }")
print(f"{B = }")

print(f'enc = "{encrypt(flag, secret_key)}"')

In another file, we are given various parameters.

n = 130480001264795511204952981970554765286628282097708497573805562495761746956689294837477924716000173700265689121058390655726461662172763702188805523675445230642476356316152454104476211773099930843629048798894397653741145611772970364363628025189743819724119397704649989182196725015667676292311250680303497618517
g = 14232999694821698106937459755169111250723143832548091913379257481041382160905011536064172867298828679844798321319150896238739468953330826850323402142301574319504629396273693718919620024174195297927441113170542054761376462382214102358902439525383324742996901035237645136720903186256923046588009251626138008729683922041672060805697738869610571751318652149349473581384089857319209790798013971104266851625853032010411092935478960705260673746033508293802329472778623222171537591292046922903109474029045030942924661333067125642763133098420446959785042615587636015849430889154003912947938463326118557965158805882580597710148
k = 109081848228506024782212502305948797716572300830339785578465230204043919222714279516643240420456408658167645175971167179492414538281767939326117482613367750888391232635306106151999375263906703485783436272382449557941704742019717763385971731987034043089865070488786181508175732060731733665723128263548176110391
A = 10331979810348166693003506393334562363373083416444082955583854323636220335613638441209816437198980825253073980493123573286927762799807446436773117670818921078297923733365129554252727963674496148945815529457095198387555733553703069705181377382893601879633657895337279524071439340411690401699779320407420258592904893010800421041848764790649945309236525529148459624417556599146885803882692326627657181584151248747924080070945415558421472606778565193931117263508570619290441914589981949634553417159683167906276897159926442471600725573380647253372071392282203683205441190912735696337884772579017885457286629133944441076065
B = 4081342267323018166249607688978380665241423816957875747125328810958590656153973787783246867777679461978030117454679495989870502705358238920918102708702013201363687875430336612386215884751792630402395947375495263771248401103245739000962715422458344125251671671250588124240486938525081520695571867300148511333511433839123962435025865462662009339451634433842267524048553313626315201481951251476302835595998914217740184369102003837614515913319042566394680732429410107620067602633793215206219823499602447575406162296590635685877032818801721681953430382920303700518722500790613216329394164889181089201919505288870098353385
enc = "abd9dd2798f4c17b9de4556da160bd42b1a5e3a331b9358ffb11e7c7b3120ed3"

So it seems here, our numbers are generated via a number $n=pq$, where $p$ and $q$ are primes. $n$ must also satisfy the property:

\[ \mathrm{gcd}(n, \varphi(n))=1 \]

From this, a number $g$ is also generated via the following rule.

\[ g = 1 + kn \]

Where $\mathrm{gcd}(k,n)=1$. This number is used to generate two other numbers $A$ and $B$ via two random integers $a$ and $b$, via the following congruences:

\[ A \equiv g^a \pmod{n^2} \] \[ B \equiv g^b \pmod{n^2} \]

Let’s expand $g$ again via the binomial expansion. I am writing $m$ here as we are trying for general integers.

\[ (1+kn)^m = 1 + mkn + \frac{m(m-1)}{m!}(kn)^2 + \ldots + (kn)^m \]

However, this expression is reduced mod $n^2$. So all terms with an $n^c$ where $c \geq 2$ will vanish to $0$.

\[ (1+kn)^m \equiv 1 + mkn \pmod{n^2} \]

Okay, so can we use this to find $m$? Let’s try to rearrange. Let $M = (1+kn)^m \pmod{n^2}$.

\[ M-1 \equiv mkn \pmod{n^2} \]

It seems we can’t reduce it any more from here… maybe? Let’s investigate the properties of $M-1$. Since $M-1 \equiv mkn \pmod{n^2}$, $M-1$ can be written as $mkn+zn^2$. $n$ can be factorised out, $mkn+zn^2 = n(mk+zn)$, so therefore $M-1$ is actually divisible by $n$ as well! So we can divide all terms in this congruence by $n$. Note that the modulo $n^2$ must also be divided by $n$.

\[ \frac{M-1}{n} \equiv mk \pmod{n} \]

Closer, but not quite there yet. How can we retrieve $m$? Well, the answer lies in this section of the code.

k = randint(2, n-1)
while gcd(k, n) != 1:
    k = randint(2, n-1)

This part is crucial. Since $\mathrm{gcd}(k,n)=1$, $k$ must have a modular inverse mod $n$. Thus if we multiply both sides by $k^{-1}$ ($k^{-1}$ denotes the modular inverse of $k \mod{n}$), we get:

\[ k^{-1}\frac{M-1}{n} \equiv m \pmod{n} \]

So we’ve formulated a congruence for the power $m$! And even better, we’re given $M, k$ and $n$! $k^{-1}$ is easy to calculate too. Let’s make a script for this. We need to find $a$, so for our purposes $M$ will be replaced by $A$ and $m$ by $a$. The value of $b$ isn’t explicitly used, only $B$ is. So we don’t need to find $b$ as well.

from Crypto.Cipher import AES
from hashlib import sha256

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n = 130480001264795511204952981970554765286628282097708497573805562495761746956689294837477924716000173700265689121058390655726461662172763702188805523675445230642476356316152454104476211773099930843629048798894397653741145611772970364363628025189743819724119397704649989182196725015667676292311250680303497618517
g = 14232999694821698106937459755169111250723143832548091913379257481041382160905011536064172867298828679844798321319150896238739468953330826850323402142301574319504629396273693718919620024174195297927441113170542054761376462382214102358902439525383324742996901035237645136720903186256923046588009251626138008729683922041672060805697738869610571751318652149349473581384089857319209790798013971104266851625853032010411092935478960705260673746033508293802329472778623222171537591292046922903109474029045030942924661333067125642763133098420446959785042615587636015849430889154003912947938463326118557965158805882580597710148
k = 109081848228506024782212502305948797716572300830339785578465230204043919222714279516643240420456408658167645175971167179492414538281767939326117482613367750888391232635306106151999375263906703485783436272382449557941704742019717763385971731987034043089865070488786181508175732060731733665723128263548176110391
A = 10331979810348166693003506393334562363373083416444082955583854323636220335613638441209816437198980825253073980493123573286927762799807446436773117670818921078297923733365129554252727963674496148945815529457095198387555733553703069705181377382893601879633657895337279524071439340411690401699779320407420258592904893010800421041848764790649945309236525529148459624417556599146885803882692326627657181584151248747924080070945415558421472606778565193931117263508570619290441914589981949634553417159683167906276897159926442471600725573380647253372071392282203683205441190912735696337884772579017885457286629133944441076065
B = 4081342267323018166249607688978380665241423816957875747125328810958590656153973787783246867777679461978030117454679495989870502705358238920918102708702013201363687875430336612386215884751792630402395947375495263771248401103245739000962715422458344125251671671250588124240486938525081520695571867300148511333511433839123962435025865462662009339451634433842267524048553313626315201481951251476302835595998914217740184369102003837614515913319042566394680732429410107620067602633793215206219823499602447575406162296590635685877032818801721681953430382920303700518722500790613216329394164889181089201919505288870098353385
enc = "abd9dd2798f4c17b9de4556da160bd42b1a5e3a331b9358ffb11e7c7b3120ed3"
enc_b = bytes.fromhex(enc)

Ak = (A - 1) // n

k_1 = modinv(k, n)

a = (k_1 * Ak) % n

key = pow(B, a, n*n)
hashkey = sha256(str(key).encode()).digest()

cipher = AES.new(hashkey, AES.MODE_ECB)
print(cipher.decrypt(enc_b))

Running this script, we get the flag!

Flag: PWNME{Thi5_1s_H0w_pAl1ier_WorKs}