Discussion @ 1141. RSA Attack @ Timus Online Judge

Miguel Angel This problem involves number theory??? [4] // Problem 1141. RSA Attack 9 Dec 2001 09:18

This problem involves number theory???

mon Re: This problem involves number theory??? [3] // Problem 1141. RSA Attack 4 Apr 2002 11:37

> This problem involves number theory???

yes, you can refer to chapter 33 of Introduction to Algorithms,
MIT Press, there covers enough knowledge you need to solve the
problem.

suppose d is multiplicative inverse of e, modulo (p - 1)(q - 1),
where p * q = n

then the answer should be c^d (mod n)

Tony Could you tell me where I can find this book? // Problem 1141. RSA Attack 10 Jul 2003 17:29

> > This problem involves number theory???
>
> yes, you can refer to chapter 33 of Introduction to Algorithms,
> MIT Press, there covers enough knowledge you need to solve the
> problem.
>
> suppose d is multiplicative inverse of e, modulo (p - 1)(q - 1),
> where p * q = n
>
> then the answer should be c^d (mod n)

Yu Xin Re: This problem involves number theory??? // Problem 1141. RSA Attack 10 Mar 2006 20:12

Thanks!

__Andrewy__ Re: This problem involves number theory??? // Problem 1141. RSA Attack 17 Aug 2016 14:40

Но ведь ответ не всегда верен! Контрпример:
e=3
n=15 (p=3,q=5)
c=3

GCD(e,(p-1)(q-1))=GCD(3,8)=1
e<(p-1)(q-1)

e*d=1 modulo (2*4) => d=3
m=c^d (modulo n)=3^3 mod (15)=(15+12) modulo (15)=12 (modulo 15) != 3 modulo (15)=c modulo (15)

Проблема возникает в случае GCD(c,n)>1 (p or q (if pq then c=0 mod (n))). Автор забыл упомянуть, что GCD(c,n)=1 или мне повезло с АС?

Edited by author 17.08.2016 14:41

Discussion of Problem 1141. RSA Attack