Next Article in Journal
Investigation of Partial Shading Scenarios on a Photovoltaic Array’s Characteristics
Next Article in Special Issue
Sensitivity Analysis for Vulnerability Mitigation in Hybrid Networks
Previous Article in Journal
Performance Evaluation of UAV-Based NOMA Networks with Hardware Impairment
Previous Article in Special Issue
RPPUF: An Ultra-Lightweight Reconfigurable Pico-Physically Unclonable Function for Resource-Constrained IoT Devices
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Small Prime Divisors Attack and Countermeasure against the RSA-OTP Algorithm

1
Digital Core Design, 41-902 Bytom, Poland
2
Department of Digital Systems, Silesian University of Technology, 44-100 Gliwice, Poland
*
Author to whom correspondence should be addressed.
Electronics 2022, 11(1), 95; https://doi.org/10.3390/electronics11010095
Submission received: 7 November 2021 / Revised: 14 December 2021 / Accepted: 24 December 2021 / Published: 28 December 2021
(This article belongs to the Special Issue Advanced Security, Trust and Privacy Solutions for Wireless Networks)

Abstract

:
One-time password algorithms are widely used in digital services to improve security. However, many such solutions use a constant secret key to encrypt (process) one-time plaintexts. A paradigm shift from constant to one-time keys could introduce tangible benefits to the application security field. This paper analyzes a one-time password concept for the Rivest–Shamir–Adleman algorithm, in which each key element is hidden, and the value of the modulus is changed after each encryption attempt. The difference between successive moduli is exchanged between communication sides via an unsecure channel. Analysis shows that such an approach is not secure. Moreover, determining the one-time password element (Rivest–Shamir–Adleman modulus) can be straightforward. A countermeasure for the analyzed algorithm is proposed.

1. Introduction

Cryptography is the basis of modern secure communication. Cryptographic algorithms are very important for the security of data or information [1]. Commonly used algorithms such as the Advanced Encryption Standard (AES) and the Secure Hash Algorithm 2 (SHA-2) are often assumed to be unbreakable. However, the predecessors of these algorithms typically experienced decreased levels of security throughout their lifetimes. Hence, despite modern algorithms appearing secure, increasingly safe solutions must be sought [2,3,4].
Commonly used algorithms are often combined with an authentication process such as one-time password (OTP) to enhance communication security. The most popular OTP implementations, known as HOTP algorithms [5], are derived from hash-based message authentication code (HMAC) [6] algorithms. Given that HMAC algorithms use hash functions as symmetric keys, they represent ideal solutions for challenge-response authentication. However, the algorithms are effectively one-way and so cannot be used directly to encrypt data. This problem is not shared by AES-based OTP authentication algorithms (AES-OTP) [7]. These two examples, despite differing in approach and algorithm utilization, both use an OTP mechanism based on non-repeating challenges with a constant cryptographic key.
Jabłoński and Wójtowicz [8] propose a novel use of the Rivest–Shamir–Adleman (RSA) [9] algorithm in the context of OTP (RSA-OTP): following each sign or encryption operation, the RSA modulus n i is replaced by a newly generated value n i + 1 . This approach ensures the secrecy of the initial key elements and their secure exchange between two communicating parties. Although this OTP-based approach no longer uses a public key, an important RSA attribute, it allows using shorter keys.
The primary advantage of RSA-OTP over AES-OTP or HOPT is a kind of one-time pad structure: each message is encrypted with a new random key which can be used for native cloning detection. A further advantage is the asymmetric nature of RSA and its mathematical simplicity. Research throughout the past four decades has shown that the primary threat to RSA is large integer factorization, a result of public knowledge of used moduli. Some research [10,11] additionally shows that the implementation method of RSA can produce unintended weaknesses. However, in the case of secret exponents and moduli, many public key RSA threats are no longer relevant.
The novel contributions of this paper are a small prime divisors attack against the RSA-OTP algorithm [8] and a countermeasure using XOR operation.

2. The RSA Algorithm

Many applications require the secure communication or storage of data. The RSA algorithm is a commonly used solution in various types of security applications. Despite the difficulty in breaking RSA keys, RSA algorithms still suffer varied attacks [12,13].
As an asymmetric encryption algorithm, RSA is widely deployed in public key cryptosystems (public key cryptography). A plaintext is encrypted by a public key and the resultant ciphertext is transmitted to the receiver where it can be decrypted by a private key. Encryption security is contingent on the difficulty of factoring the product of two large prime numbers [14].
To generate a private and public key pair, two large prime numbers p and q are randomly chosen. They are used to generate a semiprime n, where:
n = p · q ,
and Euler’s totient function φ ( n ) , where:
φ ( n ) = ( p 1 ) · ( q 1 ) .
The public key ( n , e ) is a pair, where e is an integer. Additionally, e is not a factor of mod n , and 1 < e < φ ( n ) . The private key ( n , d ) is a pair, where d is the modular multiplicative inverse of e modulo φ ( n ) :
d e 1 mod φ ( n ) .
The public key encrypts a plaintext x into a ciphertext y:
y x e mod n .
To recover the original message, the corresponding private key decrypts the ciphertext:
x y d mod n .
Example 1.
Let us choose two prime numbers p = 11 , q = 17 and compute n = 187 by means of (1). The Euler’s totient (2) is φ ( n ) = 160 . Let us choose e such that 1 < e < φ ( n ) and e and φ ( n ) are coprime: e = 7 . Let us compute a value for d (3): 23. The public key is ( e , n ) = > ( 7 , 187 ) , while the private key is ( d , n ) = > ( 23 , 187 ) . Let us encrypt letter A <ASCII 65>. The encryption (4) of x = 65 is y = 142 and the decryption (5) x of y is 65.

3. The RSA-OTP Concept

The RSA-OTP algorithm also uses asymmetric keys e and d i . Following each encrypted transaction, a new modulus generation process is initiated by one of the communicating parties. The party is hence the owner of key d i . A differential value Δ n i is created from the previous modulus n i 1 and the new modulus n i :
Δ n i = n i n i 1 .
This value is then transmitted to the second party: the owner of key e. As claimed by Jabłoński and Wójtowicz [8], Δ n i can be exchanged across a public, unsecure channel. According to the authors, such a communication method guarantees an “unconditional security level”. Moreover, the modulus length at even 128 bits should be sufficiently secure for certain applications. RSA-OTP scheme is presented in Figure 1.
Assuming the privacy of each modulus n i , 128-bit RSA-OTP can be secure under several conditions. However, given that the Δ n i values are closely related to the n i values, the unsecure exchange of Δ n i values raises serious concerns regarding unintended n i leakage. These concerns precipitate a deeper analysis of the RSA-OTP approach.
Consider the dependency between modulus n and ciphertext y within RSA, as described in Equation (4). Given that y is always smaller than n, y represents the lower bound of the range which can contain a modulus. The upper bound is the product of the two largest primes for which the bit length is equal to the maximum modulus size (e.g., 128-bit). From this, an attacker observing RSA-OTP communication can attempt to estimate the boundaries of the current moduli via Algorithm 1.
Algorithm 1k-bit RSA-OTP modulus bounding
  1:
m m i n = 2 k 1
  2:
m m a x = 2 k 1
  3:
m l = m m i n
  4:
for each ( y i , Δ n i + 1 ) R S A   O T P T R X ( ) do
  5:
    if y i > m l then
  6:
         m l y i
  7:
    end if
  8:
    if m l + Δ n i + 1 < m m i n then
  9:
         m l m m i n
10:
    else
11:
         m l m l + Δ n i + 1
12:
    end if
13:
    if m l > m m a x then
14:
         m l m m a x
15:
    end if
16:
end for
During empirical tests with 128-bit moduli, observations show that after 5 · 10 6 transactions in which ciphertext y i and differential value Δ n i are exchanged, at least twenty of the most significant bits of m l and n i match. Following this, to further reduce the security of modulus n i , the condition in which many of the most significant bits of m l are set must be detected. When this occurs, the number of possible modulus combinations decreases substantially, as shown in Table 1.
The results presented in the first two columns of Table 1 are prime number approximations generated by
π ( x ) x l o g ( x ) 1 .
Consider the smallest 128-bit number t that has its s most significant bits set (e.g., for s = 3 : t = ( 111000 000 ) 2 ). The division of t by the largest 64-bit prime number p m a x produces a lower bound p m i n of possible prime values that can generate t or greater. Determining these prime values allows the estimation of prime numbers in a given range as follows:
p r i m e N o π ( p m a x ) π ( p m i n ) .
The number of unique combinations p r i m e N o 2 represents the estimated number of possible modulus values, as displayed in the third column of Table 1. Among these combinations exist many values that do not produce sufficient “large” moduli. Such values can be justifiably included given that their existence can only be verified following the multiplication of two primes larger than p m i n . To summarize, RSA-OTP modulus leakage occurs via the following process:
  • Observation of approximately consecutive random 5 · 10 6 RSA-OTP transactions, using Algorithm 1, determines at least 20 most significant bits of each modulus.
  • Following this, the condition being reached that many of the most significant bits of m l are set brings a substantial decrease in the number of possible primes that can generate modulus n i .
Empirical tests over 32 · 10 6 RSA-OTP 128-bit transactions bounded the number of possible prime combinations that could generate the sought moduli to 91–84 bits. While this represents substantial progress toward discovering the RSA-OTP moduli, their final designation remains a computationally demanding task. Moreover, a trivial countermeasure can be applied to prevent such reduction in possible combinations of RSA-OTP moduli. This entails the verification of generated moduli and the rejection of those for which many most significant bits are set. The maximum modulus value can be limited to ( B F F F F F ) 16 . Additionally, the extension of moduli to 256-bit should make this type of attack infeasible.

4. Small Prime Divisors Attack

The RSA-OTP attack method presented in the previous section degrades security but is somewhat impractical. This section presents an alternative attack method. Three lemmas lay the framework.
Lemma 1.
If a value m 0 is a sought RSA-OTP modulus n 0 , then m 0 possesses only two divisors with bit length approximately half that of m 0 . Similarly, each of the successive moduli m 1 , m 2 , , m k 2 , m k 1 , computed by the addition of RSA-OTP Δ n i values, possess only two divisors with bit length approximately half that of the corresponding modulus.
Lemma 2.
For a prime number p and a k-element set of random numbers R = { r 0 , r 1 , , r k 2 , r k 1 } , such that r i R : r i p , the probability that p is not a divisor of any r i is p 1 p k .
Lemma 3.
Consider a set of “candidates” for RSA-OTP moduli M = { m 0 , m 1 , , m k 2 , m k 1 } which are determined using m i m i 1 = Δ n i . The RSA-OTP moduli n i are generated in a random manner such that the Δ n i = n i + 1 n i are also random. Hence, a k-element set of candidates M can be also considered random, and when it does not contain real moduli ( m i n i ), then with probability 1 p 1 p k at least one of them will be divisible by the selected, smaller prime number p.
This attack is derived from the fact that prime numbers, or large composite numbers such as RSA moduli, do not have small divisors (Lemma 1). Hence, such numbers can be “reconstructed” using equations for values that are not divisible by a set of small primes. The divisibility of integers by prime numbers is cyclic. Primes p 0 = 2 and p 1 = 3 have a cycle of 6 = l c m ( 2 , 3 ) . Primes p 0 , p 1 , and p 2 have a cycle of 30 = l c m ( 2 , 3 , 5 ) . In this manner, any value s which is non-divisible by the set of the first k primes can be described as:
s = t + p 0 · p 1 · p k 2 · p k 1 · i ,
where the offset t is an odd natural number and i is the largest natural number such that p 0 · p 1 · p k 2 · p k 1 · i < s . Hence, there exists only one possible t which is always smaller than p 0 · p 1 · p k 2 · p k 1 . Via this process, discovery of RSA moduli is undertaken by considering only odd values. As such, it holds that for every RSA-OTP modulus.
n = 1 + 2 · i 0 .
None of the practically used RSA-OTP moduli are divisible by 3, which, in conjunction with Equation (10), results in three possible offsets to describe such moduli:
n = 1 + 2 · 3 · i 1 ,
n = 3 + 2 · 3 · i 1 ,
n = 5 + 2 · 3 · i 1 .
Example 2.
Let us assume that n = 13 · 17 = 221 . It can be observed that Equation (13) holds. For the next prime, 5, noting that each offset differs by 6 = 2 · 3 = p 0 · p 1 · · p k 3 · p k 2 , the following equations must be verified:
n = 5 + 2 · 3 · 5 · i 2 ,
n = 11 + 2 · 3 · 5 · i 2 ,
n = 17 + 2 · 3 · 5 · i 2 ,
n = 23 + 2 · 3 · 5 · i 2 ,
n = 29 + 2 · 3 · 5 · i 2 .
Of these, Equation (15) holds. Hence, for the following prime, 7, the modulus n is described by an offset 11:
n = 11 + 2 · 3 · 5 · 7 · i 3 .
As l c m ( 2 , 3 , 5 , 7 , 11 ) > n (where: lcm is least common multiple), Equation (19) must determine the correct value of n, with i 3 = 1 .
Table 2 summarizes the attack. It presents the number of primes required to precisely determine moduli of set binary sizes. The attack is surprisingly effective for even 4096-bit moduli with a computational complexity on the order of 32 bits. The requirement to observe a large set of consecutive Δ n i values presents the only drawback. This follows from Lemma 2: to achieve a high probability of success, the examined set must be sufficiently large so as not to verify an offset as a false positive (i.e., non-divisible by the selected prime number).
For each subsequent small prime, the number of equations increases. As such, the discovery of the correct offset for primes larger than two appears difficult. However, the task is made considerably easier in the case of RSA-OTP by the observation of a sufficiently large set of consecutive public Δ n i values. The complete process is presented in Algorithm 2, which demonstrates the determination of the correct offset using Lemma 3. Upon validation of the correct offset, none of the checked values are divisible by the selected prime (line 18 in Algorithm 2). In another case, with probability p 1 p k (Lemma 2) some value will be divisible by the selected prime.
The designation of the RSA-OTP secret moduli makes treating them as a one-time element meaningless but does not lead to a complete breakdown of the RSA-OTP scheme: all time exponents e and d i remain unknown. However, in specific scenarios, especially for short (128/256 bit) version of RSA-OTP, it may seriously affect the secrecy of encrypted data.
Algorithm 2 Small prime divisors attack
  1:
 
Require:
  2:
b i t L e n , k , {k depends on b i t L e n , see Table 2}
  3:
{ Δ n 1 , Δ n 2 , . . . , Δ n k 2 , Δ n k 1 }
  4:
 
Ensure: { n 0 , n 1 , . . . , n k 2 , n k 1 }
  5:
l c m C y c l e { 1 , 1 }
  6:
p r i m e 2
  7:
m 0 1
  8:
for i = 1 to k 1 do
  9:
     m i m i 1 + Δ n i
10:
end for
11:
while b i t L e n g t h ( l c m C y c l e 0 ) < b i t L e n do
12:
     l c m C y c l e 0 l c m C y c l e 1
13:
     l c m C y c l e 1 l c m C y c l e 1 · p r i m e
14:
    for  i = 0   to   p r i m e 1  do
15:
         o f f s e t F i t T r u e
16:
         Δ o f f s e t i · l c m C y c l e 0 mod l c m C y c l e 1
17:
        for  j = 0   to   k 1  do
18:
            if  m j + Δ o f f s e t mod p r i m e 0  then
19:
                 o f f s e t F i t F a l s e
20:
                break
21:
            end if
22:
        end for
23:
        if  o f f s e t F i t = T r u e  then
24:
             p r i m e n e x t P r i m e ( p r i m e )
25:
            for  j = 0   to   k 1  do
26:
                 m j m j + Δ o f f s e t
27:
            end for
28:
            break
29:
        end if
30:
    end for
31:
end while
32:
 
33:
returnm

5. Countermeasures

The primary conclusion to be drawn from the presented attack is the need for secure, encrypted exchange of RSA-OTP Δ n i values. Multiple possible solutions exist, the most straightforward of which is an AES encryption algorithm. However, this approach would significantly increase the complexity of the solution. On the other hand, the Δ n i values look pseudo-random to an external observer, as shown in Figure 2. This bitmap, containing 256 randomly generated consecutive Δ n i values exchanged between communication parties, looks like (except for the few most significant bits) white noise.
Given the random nature of the Δ n i values, a more effective approach could be implemented. Consider a basic XOR operation between consecutive differential values:
Δ e n c n i = Δ n i Δ n i 1 .
Assuming Δ n 0 is a secret, random value securely exchanged between both communication sides, this approach nullifies the presented attack because an attacker cannot determine Δ n i from Δ e n c n i . As shown in Figure 3 Δ e n c n i values except for those most significant bits are approximately white noise. The figure presents a series of 256 Δ e n c n i transactions corresponded to ones in Figure 2 and Δ n 0 : 0 x F B 945 A 7 D 42485 E 3 A 0 A 5 D 2 F 346 B A A 9455 E 3 E 70682 C 2094 C A C 629 F 6 F B E D 82 C 07 C D .
The improved RSA-OTP scheme is presented in Figure 4.
The principle of operation (20) is similar to that of the Vernam cipher, because each Δ n i is derived from two randomly generated values (6) and then Δ e n c n i is a XOR result of two such consecutive values; hence, an attacker observing such communication cannot revert original value from it. As in the case of the Vernam cipher, achieving secrecy of exchanged data does not guarantee its integrity and authenticity; however, the simplicity of the mechanism increases the security of the OTP algorithm. Depending on the application, algorithms such as HMAC or Poly1305 can assure the integrity and authenticity of the Δ e n c n i approach.

6. Conclusions

The paradigm shift from constant to one-time keys is an interesting direction in the development of secure applications and services. Such an approach can potentially solve many problems regarding recovery following a system being compromised and resistance against side channel attacks. However, the case of RSA-OTP shows that exact RSA-OTP moduli delta values exchanged via insecure channels can be totally compromised, invalidating their classification as an OTP element. This is caused by the particular nature of those values: they are products of relatively large prime numbers which have no small divisors. Fortunately, despite the success of the small prime divisors attack, basic encryption via XORing consecutive differential values should prove to be a sufficient countermeasure.

Author Contributions

Conceptualization, S.S.; methodology, S.S.; software, S.S.; validation, S.S.; formal analysis, S.S.; investigation, S.S. and R.C.; resources, S.S. and R.C.; data curation, S.S.; writing—original draft preparation, S.S. and R.C.; supervision, S.S. funding acquisition, R.C. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported by the Polish Ministry of Science and Higher Education funding for statutory activities.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest.

Abbreviations

The following abbreviations are used in this manuscript:
RSARivest–Shamir–Adleman
OTPOne-Time Password
AESAdvanced Encryption Standard
HMACHash-based Message Authentication Code
HOTPHMAC OTP
XORExclusive or

References

  1. Obaid, T. Study A Public Key in RSA Algorithm. Eur. J. Eng. Technol. Res. 2020, 5, 395–398. [Google Scholar] [CrossRef]
  2. Alkim, E.; Ducas, L.; Pöppelmann, T.; Schwabe, P. Post-quantum key exchange—A new hope. In Proceedings of the 25th USENIX Security Symposium, Austin, TX, USA, 10–12 August 2016. [Google Scholar]
  3. Rajasekar, P.; Premalatha, J.; Sathya, K. Multi-factor signcryption scheme for secure authentication using hyper elliptic curve cryptography and bio-hash function. Bull. Pol. Acad. Sci. Tech. Sci. 2020, 68, 923–935. [Google Scholar] [CrossRef]
  4. Nastase, L. Security in the Internet of Things: A Survey on Application Layer Protocols. In Proceedings of the 21st International Conference on Control Systems and Computer Science (CSCS), Bucharest, Romania, 29–31 May 2017; pp. 659–666. [Google Scholar]
  5. M’Raihi, D.; Bellare, M.; Hoornaert, F.; Naccache, D.; Ranen, O. RFC4226: HOTP: An HMAC-Based One-Time Password Algorithm; RFC, Ed.; Internet Engineering Task Force (IETF): Fremont, CA, USA, 2005. [Google Scholar]
  6. Krawczyk, H.; Bellare, M.; Canetti, R. RFC2104: HMAC: Keyed-Hashing for Message Authentication; RFC, Ed.; Internet Engineering Task Force (IETF): Fremont, CA, USA, 1997. [Google Scholar]
  7. Yubico, Yubico-OTP. Available online: https://developers.yubico.com/OTP/OTPs_Explained.html (accessed on 10 November 2021).
  8. Jabłoński, J.; Wójtowicz, M. Unconditionally Secure Cryptographic System (Bezwarunkowo bezpieczny system kryptograficzny). Logistyka 2014, 12, 611–616. (In Polish) [Google Scholar]
  9. Rivest, R.; Shamir, A.; Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 1978, 21, 120–126. [Google Scholar] [CrossRef]
  10. Kocher, P. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Proceedings of the Advances in Cryptology—CRYPTO’96, Santa Barbara, CA, USA, 18–22 August 1996; pp. 104–113. [Google Scholar]
  11. Karbownik, P.; Russek, P.; Wiatr, K. Weak RSA Keys Discovery on GPGPU. Int. J. Electron. Telecommun. 2019, 65, 25–31. [Google Scholar] [CrossRef]
  12. Overmars, A.; Venkatraman, S. Mathematical Attack of RSA by Extending the Sum of Squares of Primes to Factorize a Semi-Prime. Math. Comput. Appl. 2020, 25, 63. [Google Scholar] [CrossRef]
  13. Ariffin, M.R.K.; Abubakar, S.I.; Yunos, F.; Asbullah, M.A. New Cryptanalytic Attack on RSA Modulus N=pq Using Small Prime Difference Method. Cryptography 2019, 3, 2. [Google Scholar] [CrossRef] [Green Version]
  14. Yan, S.Y. Factoring Based Cryptography. In Cyber Cryptography: Applicable Cryptography for Cyberspace Security; Springer: Berlin/Heidelberg, Germany, 2018; pp. 217–286. [Google Scholar]
Figure 1. RSA-OTP scheme.
Figure 1. RSA-OTP scheme.
Electronics 11 00095 g001
Figure 2. Example bitmap of 256 Δ n i values from following 256-bit RSA-OTP random transactions (one value per row). (1) 0 x 27 C B B 0 E A D A 66 F 8 C 1 A 8 F A 444 A 1 D 738 E 4 E 124 F 38 F 0 A 0 C 5 C D 10 110066 E 9724 D A A F 5 *. (2) 0 x 5 B 8 D 5 B 5 B 9 D E 5 E 771319 C E F 62 D 99 C F 5169 B 994 F 7 D D 34 C D B C 2 F 45462 B 79 7 D 7 E 9 D 8 * (256) 0 x 5 D 38 F B A F B 2 A 93048 A A 4850 C E 4 B 70 E 3 A 26 E 8 C 0 B D 4 C 130 F F 5 F 4 F 6135 4 F 4 A 7371 B 6 *. * The least significant bit of each value is a sign bit (1: negative, 0: positive).
Figure 2. Example bitmap of 256 Δ n i values from following 256-bit RSA-OTP random transactions (one value per row). (1) 0 x 27 C B B 0 E A D A 66 F 8 C 1 A 8 F A 444 A 1 D 738 E 4 E 124 F 38 F 0 A 0 C 5 C D 10 110066 E 9724 D A A F 5 *. (2) 0 x 5 B 8 D 5 B 5 B 9 D E 5 E 771319 C E F 62 D 99 C F 5169 B 994 F 7 D D 34 C D B C 2 F 45462 B 79 7 D 7 E 9 D 8 * (256) 0 x 5 D 38 F B A F B 2 A 93048 A A 4850 C E 4 B 70 E 3 A 26 E 8 C 0 B D 4 C 130 F F 5 F 4 F 6135 4 F 4 A 7371 B 6 *. * The least significant bit of each value is a sign bit (1: negative, 0: positive).
Electronics 11 00095 g002
Figure 3. Example bitmap of 256 Δ e n c n i values from following 256-bit RSA-OTP random transactions (one value per row). (1) 0xDC5FEA97982EA6FBA2A76B7E76D91A1BF1A83E7262CC81BC739F0957AA61AD38. (2) 0x7C46EBB147831FB09966AB28C4EF7B5889D6778D738916D2E554045EE59A432C (256) 0x177 A17001C0DAC110B7F4EDF42428ABC497E54C5684E0A737C7EC7BE2FD6DC08.
Figure 3. Example bitmap of 256 Δ e n c n i values from following 256-bit RSA-OTP random transactions (one value per row). (1) 0xDC5FEA97982EA6FBA2A76B7E76D91A1BF1A83E7262CC81BC739F0957AA61AD38. (2) 0x7C46EBB147831FB09966AB28C4EF7B5889D6778D738916D2E554045EE59A432C (256) 0x177 A17001C0DAC110B7F4EDF42428ABC497E54C5684E0A737C7EC7BE2FD6DC08.
Electronics 11 00095 g003
Figure 4. Improved RSA-OTP scheme.
Figure 4. Improved RSA-OTP scheme.
Electronics 11 00095 g004
Table 1. Summary of RSA-OTP moduli security as a function of the number of known most significant bits (MSBs) of 128-bit moduli.
Table 1. Summary of RSA-OTP moduli security as a function of the number of known most significant bits (MSBs) of 128-bit moduli.
Number of Modulus MSBs SetSecurity Level in BitsApproximate Number of Observed RSA-OTP Transactions After Which, with Probability p = 1 2 , Some Modulus Will Have a Distinct Number of MSBs Set
11151
21132
31118
1881 2 33
1979 2 35
2077 2 37
Table 2. hlSummary of the RSA-OTP small prime division attack.
Table 2. hlSummary of the RSA-OTP small prime division attack.
k-th Prime Number p k 1 Prime NumberBit Length of RSA-OTP ModulusNumber of Observed Δ n i Values for Attack Error Probability e = 10 15 Estimated Attack Complexity (Bits)
26101128347220
44193256664922
7638351213,21223
132743102425,64626
2341481204851,13529
41928974096100,04232
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Sarna, S.; Czerwinski, R. Small Prime Divisors Attack and Countermeasure against the RSA-OTP Algorithm. Electronics 2022, 11, 95. https://doi.org/10.3390/electronics11010095

AMA Style

Sarna S, Czerwinski R. Small Prime Divisors Attack and Countermeasure against the RSA-OTP Algorithm. Electronics. 2022; 11(1):95. https://doi.org/10.3390/electronics11010095

Chicago/Turabian Style

Sarna, Szymon, and Robert Czerwinski. 2022. "Small Prime Divisors Attack and Countermeasure against the RSA-OTP Algorithm" Electronics 11, no. 1: 95. https://doi.org/10.3390/electronics11010095

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop