Certifying RSA

Saqib A. Kakvi*, Eike Kiltz, Alexander May

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

16 Citations (Scopus)

Abstract

We propose an algorithm that, given an arbitrary N of unknown factorization and prime e ≥ N1/4+ε, certifies whether the RSA function RSAN,e(x): = xe mod N defines a permutation over ℤN* or not. The algorithm uses Coppersmith's method to find small solutions of polynomial equations and runs in time O(ε-8 log2 N). Previous certification techniques required e > N.

Original languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages404-414
Number of pages11
Volume7658 LNCS
DOIs
Publication statusPublished - 2012
Event18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012 - Beijing, China
Duration: 2 Dec 20126 Dec 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7658 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012
CountryChina
CityBeijing
Period2/12/126/12/12

Keywords

  • Certified trapdoor permutations
  • Coppersmith
  • RSA

Fingerprint Dive into the research topics of 'Certifying RSA'. Together they form a unique fingerprint.

Cite this