The RSA cryptosystem consists of a public key and a private key. Messages are encrypted using the public key and decrypted using the private key. The public key consists of the numbers
and
, and encryption is performed using the following formula:
, where
is the message being encrypted. The message must be represented by an integer satisfying
, and
is the resulting ciphertext.
To decrypt the message, we need to calculate 
, the private exponent, as the modular inverse of modulo 
. In other words, is a number satisfying 
, where is Euler’s totient function. It gives the number of positive integers less than or equal to that are relatively prime to . Decryption is performed using the formula 
, where is the ciphertext and is the decrypted message.
Given 
, 
, and 
, can you decrypt without knowing the private key?
[lang=hr]
RSA kriptosustav sastoji se od javnog i privatnog ključa. Poruke šifriramo javnim, a dešifriramo privatnim ključem. Javni ključ sastoji se od brojeva $N$ i $e$, a šifriranje se radi po ovoj formuli: $c = m^e \pmod{N}$, gdje je $m$ poruka koju šifriramo (jasno je da mora vrijediti $0 \leq m < N$), a $c$ je dobiveni šifrat.
Za dešifriranje potrebno je izračunati $d$ (privatni eksponent) kao modularni inverz od $e$ modulo $\varphi(N)$. Drugim riječima, $d$ je broj takav da vrijedi $ed \equiv 1 \pmod{\varphi(N)}$, a $\varphi(N)$ je Eulerova funkcija koja vraća broj brojeva manjih ili jednakih $N$ koji su relativno prosti s $N$. Dešifriranje se radi formulom $m = c^d \pmod{N}$, gdje je $c$ šifrat, a $m$ poruka koju smo dešifrirali.
Zadano je $N = 454561$, $e = 3$ i $c = 173596$. Možeš li bez privatnog ključa dešifrirati $c$?
[/lang]
[lang=en]
The RSA cryptosystem consists of a public key and a private key. Messages are encrypted using the public key and decrypted using the private key. The public key consists of the numbers $N$ and $e$, and encryption is performed using the following formula: $c = m^e \pmod{N}$, where $m$ is the message being encrypted. The message must be represented by an integer satisfying $0 \leq m < N$, and $c$ is the resulting ciphertext.
To decrypt the message, we need to calculate $d$, the private exponent, as the modular inverse of $e$ modulo $\varphi(N)$. In other words, $d$ is a number satisfying $ed \equiv 1 \pmod{\varphi(N)}$, where $\varphi(N)$ is Euler’s totient function. It gives the number of positive integers less than or equal to $N$ that are relatively prime to $N$. Decryption is performed using the formula $m = c^d \pmod{N}$, where $c$ is the ciphertext and $m$ is the decrypted message.
Given $N = 454561$, $e = 3$, and $c = 173596$, can you decrypt $c$ without knowing the private key?
[/lang]
