Certifying RSA

Saqib A. Kakvi; Eike Kiltz; Alexander May

doi:10.1007/978-3-642-34961-4_25

Certifying RSA

Saqib A. Kakvi^*, Eike Kiltz, Alexander May

^*Corresponding author for this work

Department of Computer Science

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

20 Citations (Scopus)

Abstract

We propose an algorithm that, given an arbitrary N of unknown factorization and prime e ≥ N^1/4+ε, certifies whether the RSA function RSA_N,e(x): = x^e 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 log² N). Previous certification techniques required e > N.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	404-414
Number of pages	11
Volume	7658 LNCS
DOIs	https://doi.org/10.1007/978-3-642-34961-4_25
Publication status	Published - 2012
Event	18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012 - Beijing, China Duration: 2 Dec 2012 → 6 Dec 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7658 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012
Country/Territory	China
City	Beijing
Period	2/12/12 → 6/12/12

Keywords

Certified trapdoor permutations
Coppersmith
RSA

Access to Document

10.1007/978-3-642-34961-4_25

Handle.net

Persistent link

Cite this

Kakvi, S. A., Kiltz, E., & May, A. (2012). Certifying RSA. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 7658 LNCS, pp. 404-414). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7658 LNCS). https://doi.org/10.1007/978-3-642-34961-4_25

@inproceedings{5f6c7e8d5ced4f91bfde2ba4de973a7d,

title = "Certifying RSA",

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.",

keywords = "Certified trapdoor permutations, Coppersmith, RSA",

author = "Kakvi, {Saqib A.} and Eike Kiltz and Alexander May",

year = "2012",

doi = "10.1007/978-3-642-34961-4_25",

language = "English",

isbn = "9783642349607",

volume = "7658 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "404--414",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

note = "18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012 ; Conference date: 02-12-2012 Through 06-12-2012",

}

Kakvi, SA, Kiltz, E & May, A 2012, Certifying RSA. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 7658 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7658 LNCS, pp. 404-414, 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012, Beijing, China, 2/12/12. https://doi.org/10.1007/978-3-642-34961-4_25

Certifying RSA. / Kakvi, Saqib A.; Kiltz, Eike; May, Alexander.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7658 LNCS 2012. p. 404-414 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7658 LNCS).

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

TY - GEN

T1 - Certifying RSA

AU - Kakvi, Saqib A.

AU - Kiltz, Eike

AU - May, Alexander

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Certified trapdoor permutations

KW - Coppersmith

KW - RSA

UR - http://www.scopus.com/inward/record.url?scp=84871568449&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-34961-4_25

DO - 10.1007/978-3-642-34961-4_25

M3 - Conference Contribution (Conference Proceeding)

AN - SCOPUS:84871568449

SN - 9783642349607

VL - 7658 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 404

EP - 414

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012

Y2 - 2 December 2012 through 6 December 2012

ER -

Kakvi SA, Kiltz E, May A. Certifying RSA. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 7658 LNCS. 2012. p. 404-414. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-34961-4_25

Certifying RSA

Abstract

Publication series

Conference

Keywords

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this