UOJ Logo ChthollyODT的博客

博客

Correctness Proof of RSA Algorithm Decryption

2023-03-03 21:24:30 By ChthollyODT

As we all known $c = m^e (mod\ n)$, so $m \equiv c^d (mod\ n) \equiv m^{ed} (mod\ n) \equiv m(mod\ φ(n)) \equiv m^{kφ(n)+1}(mod\ n)$,so we only need to prove that $m \equiv m^{kφ(n)+1}(mod\ n)$

Divided into two situations:

  1. $m$ and $n$ are mutually prime

By Euler's theorem $m^{φ(n)} \equiv 1 (mod\ n)$ ,so

$m^{kφ(n)} \equiv 1^k (mod\ n)$

$m^{kφ(n)} \equiv 1 (mod\ n)$

$m^{kφ(n)+1} \equiv m (mod\ n)$

  1. $m$ and $n$ are not mutually prime

Let $m < n$, $p$ and $q$ are both prime numbers, which means $m$ is either a multiple of $p$ or a multiple of $q$, and can't be a multiple of both $p$ and $q$ (if it is a multiple of both $p$ and $q$ , then let $m > n$), let $m$ be a multiple of $p$, then $m = cp$, where $c$ is positive, then $gcd(m, q) = 1$, according to Euler's theorem:

$m^{φ(q)} \equiv 1 (mod\ q)$

So

$m^{kφ(q)} \equiv 1 (mod\ q)$

$(m^{kφ(q)})^{φ(p)} \equiv 1^{φ(p)} (mod\ q)$

$(m^{kφ(q)})^{φ(p)} \equiv 1 (mod\ q)$

$m^{kφ(n)} \equiv 1 (mod\ q)$

Therefore, there exists an integer $r$ such that $m^{kφ(n)} = 1 + rq$, multiply both sides by $m = cp$, we can get:

$m^{kφ(n)+1} = m + rcpq = m + rcn$

The result is :

$m^{kφ(n)+1} \equiv m (mod\ n)$

In summary, regardless of whether m and n are mutually prime, RSA can correctly decrypt the message

评论

ChthollyODT
是hw啦QWQ
Dictionembrownedge
看不懂

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。