Collision in the DSA Function

Igor E. Shparlinski*, Ron Steinfeld

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

We study possible collisions among the values of the DSA function f(s) = (g(s) rem p) rem t where g is order t modulo a prime p and n rem k denotes the remainder of n on division by k. In particular, in a certain range of p and t we guarantee the existence of collisions and also give a nontrivial algorithm for inverting this function.

Original languageEnglish
Title of host publicationCoding and cryptology
EditorsY Li, S Ling, H Niederreiter, H Wang, C Xing, S Zhang
Place of PublicationNew Jersey
PublisherWorld Scientific Publishing
Pages226-232
Number of pages7
ISBN (Print)9789812832238
Publication statusPublished - 2008
Event1st International Workshop on Coding and Cryptology - Fujian, China
Duration: 11 Jun 200715 Jun 2007

Publication series

NameSeries on Coding Theory and Cryptology
PublisherWorld Scientific Publishing Co Pte Ltd
Volume4
ISSN (Print)1793-2238

Conference

Conference1st International Workshop on Coding and Cryptology
CountryChina
CityFujian
Period11/06/0715/06/07

Keywords

  • DSA function
  • collisions
  • UNFORGEABLE SIGNATURES

Cite this