👎 -21

Number theory nujna pomosh

. Suppose that a plaintext message P is not relatively prime to n = pq;
where p and q are large primes Is it possible to successfully decrypt the
ciphertext produced by encrypting P using RSA cryptosystem. with key (e; n)?

криптография высшая математика математика обучение     #1   18 апр 2021 20:52   Увидели: 12 клиентов, 1103 специалиста   Ответить
👎 0

Unfortunately this engine does not support TeX, sorry for the bad handwriting.

In fact RSA works for all $P\in Z/p+Z/q$.
If P is invertible in the ring Z/p+Z/q, then $P^{d e}=P mod n$ by the construction: $de=1 mod \phi(n)$, where Euler function $\phi(n)=|(Z/p+Z/q)^*|$ is equal to the number of invertible elements of the ring. Here $d,e$ is a pair of decryption/encryption keys. Hence we can exploit the fact that $P^\phi(n)=1 mod n$ to show that $P^{de}=P mod n$.
If P is not invertible, then $P^\phi(pq)$ is not equal to 1 in the ring, nonetheless $P^{d e}=P mod n$. For example, if $P=(0,a)\in Z/p+Z/q$, then $P^{\phi(n)}=(0,1)$, thus $P^{de}=P mod n$ and the desired equality holds.

Задайте свой вопрос по высшей математике

Сейчас онлайн 75 репетиторов по высшей математике
Получите ответ профи быстро и бесплатно
ASK.PROFI.RU © 2020-2021