Ask Your Question
1

Tonelli-Shank values are incorrect when trying to get back to c value for Rabin

asked 2020-10-29 00:27:13 +0100

anything gravatar image

updated 2020-10-31 08:29:25 +0100

FrédéricC gravatar image

I'm working (banging head against wall) on a Rabin encryption as part of a challenge. I thought I was making progress as several algorithms had given em the same values for the mod sqrt but it seems that they are incorrect as I cannot get back to c from them but I don't understand why.

If someone can explain why they might be wrong or where I am going wrong that would be fantastic, thank you.

My values are:

n = 64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271842214498048655106618080254509684622363068406743573918979874641476333101257493419006081088753833559346504226066744706781644205324359031963711461737816475092631177676839385116576945754784715871099567521310291121

p = q = 8043878802952623586394638108236704902850439411184561583961128617599719871469109041598304494567727280429349828456316270041563810531926784203271836896365511

roots = 
2187931274452861858404184425736861076518005991476611501855956036160679792394841793895180158176546375577356726244165298846056538405976359097397665134536364 

5855947528499761727990453682499843826332433419707950082105172581439040079074267247703124336391180904851993102212150971195507272125950425105874171761829147

However when getting back to c the assertion fails, there is a link here: - I cannot post link but the query param for sage cell is ?q=lnopxn

any help would be fantastic, I'm an incompetent fool at the best of times but I feel I should be closer to this and I am and simply cannot understand why the roots are considered wrong when several different algorithms have given the same results.

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
0

answered 2020-10-31 12:09:40 +0100

rburing gravatar image

It seems you have found two solutions $r_1,r_2$ to the equation $r^2 = c \pmod p$, instead of modulo $n=p^2$.

These can be lifted to solutions of $r^2 = c \pmod n$ as explained in Tonelli's 1891 note:

sage: x1 = r1.powermod(p, n) * c.powermod((n - 2*p + 1)/2, n) % n
sage: x1
64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271753034649923142113830515792268064444518487016929096020442400942507965121543243161654445051643484581747767916266843209412116392813513581705574559159767553746511654597410103495145251789022071249050813249711591476
sage: (x1^2 - c) % n
0
sage: x2 = (-x1) % n
sage: x2
89179848125512992787564462241620177844581389814477898537473698968367979714250257351636037110348977598736309799901497369527812510845450258136902578048921346119523079429281621431693965762644622048754271598699645
sage: (x2^2 - c) % n
0
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-10-29 00:27:13 +0100

Seen: 420 times

Last updated: Oct 31 '20