The Miller–Rabin test with randomized exponents
We analyze a variant of the well-known Miller–Rabin test, that may be useful in preventing side-channel attacks to the random prime generation on smart cards: In the Miller–Rabin primality test for a positive integer n, one computes repeatedly the expression aω (mod n) for random bases a ∈ ℕ and exp...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2009-12-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/JMC.2009.019 |
| _version_ | 1828109615642968064 |
|---|---|
| author | Böckle Gebhard |
| author_facet | Böckle Gebhard |
| author_sort | Böckle Gebhard |
| collection | DOAJ |
| description | We analyze a variant of the well-known Miller–Rabin test, that may be useful in preventing side-channel attacks to the random prime generation on smart cards: In the Miller–Rabin primality test for a positive integer n, one computes repeatedly the expression aω (mod n) for random bases a ∈ ℕ and exponents ω such that ω divides n – 1 and (n – 1)/ω is a power of 2. In each round one chooses, at random, a different base a, and uses binary exponentiation to compute aω (mod n). ‘Listening’ to many rounds, it seems at least plausible that an outside spy could retrieve the integer n – 1. |
| first_indexed | 2024-04-11T11:05:57Z |
| format | Article |
| id | doaj.art-1406fe254611401ba334d19d3766de16 |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-11T11:05:57Z |
| publishDate | 2009-12-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-1406fe254611401ba334d19d3766de162022-12-22T04:28:21ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842009-12-013430731910.1515/JMC.2009.019The Miller–Rabin test with randomized exponentsBöckle Gebhard0Fakultät für Mathematik, Universität Duisburg-Essen, Campus Essen, 45117 Essen, Germany. Email: gebhard.boeckle@uni-due.deWe analyze a variant of the well-known Miller–Rabin test, that may be useful in preventing side-channel attacks to the random prime generation on smart cards: In the Miller–Rabin primality test for a positive integer n, one computes repeatedly the expression aω (mod n) for random bases a ∈ ℕ and exponents ω such that ω divides n – 1 and (n – 1)/ω is a power of 2. In each round one chooses, at random, a different base a, and uses binary exponentiation to compute aω (mod n). ‘Listening’ to many rounds, it seems at least plausible that an outside spy could retrieve the integer n – 1.https://doi.org/10.1515/JMC.2009.019miller–rabin testsecure prime generationside channel attacks |
| spellingShingle | Böckle Gebhard The Miller–Rabin test with randomized exponents Journal of Mathematical Cryptology miller–rabin test secure prime generation side channel attacks |
| title | The Miller–Rabin test with randomized exponents |
| title_full | The Miller–Rabin test with randomized exponents |
| title_fullStr | The Miller–Rabin test with randomized exponents |
| title_full_unstemmed | The Miller–Rabin test with randomized exponents |
| title_short | The Miller–Rabin test with randomized exponents |
| title_sort | miller rabin test with randomized exponents |
| topic | miller–rabin test secure prime generation side channel attacks |
| url | https://doi.org/10.1515/JMC.2009.019 |
| work_keys_str_mv | AT bocklegebhard themillerrabintestwithrandomizedexponents AT bocklegebhard millerrabintestwithrandomizedexponents |