# How to decrypt Rabin message when p=q and you have the roots from Tonelli-Shanks

I've been trying to decrypt a message encrypted with Rabin as a challenge. I'm very new to cryptography and these challenges so much of this is new.

I've factorised n and determined that p=q which I understand to be incredibly weak. After many hours I discovered that the proposed decryption using extended gcd will not work.

A similar post on this site suggested using Tonelli Shanks to get the roots, which I have done. It then went on to say to use Hensel to then get the original values which will then help me decode the message, however I am unfamiliar with how to implement this and so far have not been able to get a sensible solution so would like to ask for help.

My values are:

n = 64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271842214498048655106618080254509684622363068406743573918979874641476333101257493419006081088753833559346504226066744706781644205324359031963711461737816475092631177676839385116576945754784715871099567521310291121
c = 60176314581676071043291067556352196274798660837188399828657574988742539250919925123769575021091715252070984470036260674221672743791229186519807702970426856963367776191049481817101068301897617186674960557150362771617316082251276579987076557148986523477838971190589062577795308359830070072697195634741564991953
p = q = 8043878802952623586394638108236704902850439411184561583961128617599719871469109041598304494567727280429349828456316270041563810531926784203271836896365511
root0 = 2187931274452861858404184425736861076518005991476611501855956036160679792394841793895180158176546375577356726244165298846056538405976359097397665134536364
root1 = 5855947528499761727990453682499843826332433419707950082105172581439040079074267247703124336391180904851993102212150971195507272125950425105874171761829147

• Comments are not for extended discussion; this conversation has been moved to chat.
– fgrieu
Commented Oct 29, 2020 at 6:28

We are given $$n>4$$ and ciphertext $$c\in(0,n)$$ for textbook Rabin encryption. We want to solve for $$x\in[0,n)$$ the equation $$x^2\bmod n=c$$. We found that $$n$$ is a square, computed $$p=\sqrt n$$, found that it is prime, solved $$y^2\bmod p=c\bmod p$$ yielding two roots $$y_0\in(0,p/2)$$ and $$y_1=p-y_0$$, and now want the solutions for the original equation.

Every $$x\in[0,n)$$ can be uniquely written as $$x=y+z\,p$$ with $$y\in[0,p)$$ and $$z\in[0,p)$$.
If $$x=y+z\,p$$ is a solution of $$x^2\equiv c\pmod{p^2}$$, then that also yield modulo $$p$$ since $$p$$ divides $$p^2$$, thus $$y^2\equiv c\pmod p$$, thus our earlier work did yield the possible values of $$y$$.

Now $$(y+z\,p)^2\equiv c\pmod{p^2}$$ becomes $$y^2+2\,y\,z\,p\equiv c\pmod{p^2}$$, that is
$$2\,y\,z\,p\equiv c-y^2\pmod{p^2}$$, that is
$$\exists k\in\mathbb Z,\,2\,y\,z\,p+k\,p^2=c-y^2$$, that is
$$\exists k\in\mathbb Z,\,2\,y\,z+k\,p=(c-y^2)/p$$, that is
$$c-y^2$$ is divisible by $$p$$ and $$2\,y\,z\equiv(c-y^2)/p\pmod p$$, that is
$$c-y^2$$ is divisible by $$p$$ and $$z\equiv(2\,y)^{-1}\,((c-y^2)/p)\pmod p$$

Thus we check that $$c-{y_0}^2\bmod p=0$$ (which must hold unless we goofed in computing $$y_0$$),
compute $$b_0=(c-{y_0}^2)/p\bmod p$$, then $$z_0=(2\,y_0)^{-1}\,b_0\bmod p$$,
then $$x_0=y_0+z_0\,p$$, and that's one solution. It can't be zero. The other is $$x_1=p^2-x_0$$.