TIME: 1:30-2:20 pm, April 4, 2006

PLACE: CSE 403

TITLE: A New Related Message Attack on RSA

SPEAKER:  Yacov Yacobi
                    Microsoft Research

ABSTRACT:  Coppersmith, Franklin, Patarin, and Reiter show that given two RSA cryptograms  x^e mod N  and  (ax+b)^e mod N  for known constants a,b Î Z_N , one can usually compute x in O(elog²e)  Z_N -operations (there are O(e²) messages for which the method fails).

We show that given e  cryptograms c_i ≡(a_i x+b_i )^e mod N,  i=0,1,...e-1,  for any known constants a_i ,b_i Î Z_N ,  one can deterministically compute x  in O(e) Z_N -operations that depend on the cryptograms, after a pre-processing that depends only on the constants. The complexity of the pre-processing is O(elog²e)  Z_N- operations, and can be amortized over many instances.  We also consider a special case where the overall cost of the attack is O(e)  Z_N -operations.  Our tools are borrowed from numerical-analysis and adapted to handle formal polynomials over finite-rings.  To the best of our knowledge their use in cryptanalysis is novel.

Joint with Oded Yacobi, Mathematics Department, University of California, San Diego.

 

This work was published in Public Key Cryptography 2005.   A journal version will appear in the book: Essays in Theoretical  Computer Science in Memory of Shimon Even. Springer's LNCS.