Score:0

How to find iteration exponent in a cycling attack?

cn flag

In Simmons and Norris paper they demonstrate the cycling attack with the following example:

p = 383 q = 563 s = 49 and t = 56957 ( a prime)

The attacker knows the publicly available r = pq = 215,629 , s = 49 and an encrypted message C. By forming C1 = C49 , C2 = C149, etc. He will find Cj = C for 1,2,5 or 10

I do not understand how they figured out they will have M = Cj-1 in at most 10 steps? They do mention that 49 belongs to the exponent 10 mod φ(r) = 214,684 but I am not sure what that means. Could anyone explain? please. Thank you!

fgrieu avatar
ng flag
The paper referenced is : Gustavus J. Simmons & Michael J. Norris (1977) PRELIMINARY COMMENTS ON THE M.I.T. PUBLIC-KEY CRYPTOSYSTEM, Cryptologia, 1:4, 406-414, [paywalled](https://doi.org/10.1080/0161-117791833219).
kelalaka avatar
in flag
[Cycle attack on RSA](https://crypto.stackexchange.com/q/1572/18298)
Score:2
ru flag

A cycling attack with encryption exponent $s$ relies on $s$ having small multiplicative order modulo the multiplicative order of the ciphertext. If $c^v\equiv 1\pmod{pq}$ and $s^w\equiv 1\pmod v$ then repeatedly encrypting $c$ for $w$ times gives $$c^{s\times s\times\cdots\times s\times s}\equiv c^{s^w}\pmod{pq}.$$ We know that $s^w=kv+1$ for some $k$ so that $$c^{s^w}=c^{kv}c\equiv c\pmod{pq}.$$

In your case $pq=215629$ and $s=49$. so we know that $v$ divides $\phi(pq)=214684$. This tells us that $w$ divides the multiplicative order of $s$ modulo 214684. A simple calculation will show that $$49^{10}\equiv 1\pmod{214684}$$ so that $w$ must divide 10. There will be values of $w$ smaller than 10 for some values of $c$ (e.g. $c=32$).

If we write $\mathrm{ord}(x,m)$ for the multiplicative order of $x$ modulo $m$ (i.e. the smallest integer $t>0$ such that $x^t\equiv 1\pmod m$ then the general expression for the number of iterations is $$\mathrm{ord}\left(s,\mathrm{ord}(c,pq)\right).$$

cn flag
perfect! makes sense. thanks!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.