Làm thế nào để tìm số mũ lặp lại trong một cuộc tấn công đi xe đạp?

Một cuộc tấn công đi xe đạp với số mũ mã hóa $s$ dựa vao $s$ có cấp số nhân nhỏ modulo cấp số nhân của bản mã. Nếu $c^v\equiv 1\pmod{pq}$ và $s^w\equiv 1\pmod v$ sau đó liên tục mã hóa $c$ vì $w$ thời gian cho $$c^{s\times s\times\cdots\times s\times s}\equiv c^{s^w}\pmod{pq}.$$ Chúng ta biết rằng $s^w=kv+1$ cho một số $k$ để có thể $$c^{s^w}=c^{kv}c\equiv c\pmod{pq}.$$

Trong trường hợp của bạn $pq=215629$ và $s=49$. vì vậy chúng tôi biết rằng $v$ phân chia $\phi(pq)=214684$. Điều này cho chúng ta biết rằng $w$ chia thứ tự nhân của $s$ modulo 214684. Một phép tính đơn giản sẽ chỉ ra rằng $$49^{10}\equiv 1\pmod{214684}$$ để có thể $w$ phải chia hết cho 10. Sẽ có các giá trị của $w$ nhỏ hơn 10 đối với một số giá trị của $c$ (ví dụ. $c=32$).

Nếu chúng ta viết $\mathrm{ord}(x,m)$ cho thứ tự nhân của $x$ modulo $m$ (tức là số nguyên nhỏ nhất $t>0$ như vậy mà $x^t\equiv 1\pmod m$ thì biểu thức chung cho số lần lặp lại là $$\mathrm{ord}\left(s,\mathrm{ord}(c,pq)\right).$$