### Abstract

Let N = pq denote an RSA modulus of length n bits. Call N an (m − LSbS) RSA modulus if p and q have exactly m equal Least Significant (LS) bits. In Asiacrypt `98, Boneh, Durfee and Frankel (BDF) described several interesting `partial key exposure' attacks on the RSA system. In particular, for low public exponent RSA, they show how to recover in time polynomial in n the whole secret-exponent d given only the n=4 LS bits of d. In this note, we relax a hidden assumption in the running time estimate presented by BDF for this attack. We show that the running time estimated by BDF for their attack is too low for (m− LSbS) RSA moduli by a factor in the order of 2^{m}. Thus the BDF attack is intractable for such moduli with large m. Furthermore, we prove a general related result, namely that if low-exponent RSA using an (m − LSbS) modulus is secure against poly-time conventional attacks, then it is also secure against poly-time partial key exposure attacks accessing up to 2m LS bits of d. Therefore, if low-exponent RSA using (n=4(1 − ɛ) − LSbS) moduli for small ɛ is secure, then this result (together with BDF's result on securely leaking the n=2 MS bits of d) opens the possibility of fast and secure public-server-aided RSA decryption/signature generation.

Original language | English |
---|---|

Title of host publication | Topics in Cryptology - CT-RSA 2001 - The Cryptographers’ Track at RSA Conference 2001, Proceedings |

Editors | David Naccache |

Place of Publication | Berlin Germany |

Publisher | Springer |

Pages | 52-62 |

Number of pages | 11 |

ISBN (Electronic) | 3540418989, 9783540418986 |

DOIs | |

Publication status | Published - 2001 |

Event | Cryptographers' Track at RSA Conference, CT-RSA 2001 - San Francisco, United States of America Duration: 8 Apr 2001 → 12 Apr 2001 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 2020 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Cryptographers' Track at RSA Conference, CT-RSA 2001 |
---|---|

Abbreviated title | CT-RSA 2001 |

Country | United States of America |

City | San Francisco |

Period | 8/04/01 → 12/04/01 |

## Cite this

*Topics in Cryptology - CT-RSA 2001 - The Cryptographers’ Track at RSA Conference 2001, Proceedings*(pp. 52-62). (Lecture Notes in Computer Science; Vol. 2020). Springer. https://doi.org/10.1007/3-540-45353-9_5