Quadratic Ciphers - Introduction to Cryptography with Java Applets - page 194

send the same message P to 2 entities, having moduli n , and n *. They would compute the

lnr's of

C P

2 (mod

n

)

C *

P

2 (mod

n *).

Since it is very likely that these 2 moduli are pairwise relatively prime, one can easily
compute a simultaneous solution modulo M = n n * for x to the set of congruences

x C (mod n )

x C * (mod n *).

2 < n n *, by CRT we must have x = P 2 . Thus, by merely taking the normal pos-

Since P

itive square root of x , one can obtain P .

E XAMPLE . In this example, we will use parameters which would be feasible in actual prac-
tice. I think this is important for examples in cryptanalysis, to give you an idea of the scope
of the problem. Suppose we wish to send the message

m =
327562836508236509237590237590823750923875098275908237590827359082375908
723095873209875093285790328750932875093248750983275098327509832759082375
098370957309287509328750923858723658972365892365930275094327590342857326
589726598235698236598235689265892365095780936723985689236598236598236598
236598236598256982569823569826539823659826985273209568923658923793286598
2365982365987263986598236589726895698236598236598723658972

to two different entities using Rabin. The first entity uses the public modulus

n =

646340121426220146014297533773399039208882053394309680642606908550493102
777357817863944028230458269273774359218437960389882391183009818421901763
047728965662412617547346019921835003955007793042135921152767681351365535
844372852395123236761886769523409411632917040726100857751517830821316172
151047982478607716803918058340827477683169176315227971638380003141234015
213715286981934574126958310812212353843734392842382104560615275941849712
736764525520559801471208444488841303619868703237828364738114662819239227
238184943188233259835607113670605755573747578481214665113626049865412769
43834825366579731809108470421496863793133,

and the second uses the modulus

n * =

827315355425561786898300843229950770187369028344716391222536842944631171
555018006865848356134986584670431179799600589299049460714252567580034256
701093076047888150460602905499948805062409975093933979075542632129747885