DM-RSA-OAEP: Formal Treatment of a Dual-Modulus Fault-Detection Countermeasure Based on Physical Diversity

DM-RSA-OAEP: Formal Treatment of a Dual-Modulus Fault-Detection Countermeasure Based on Physical Diversity ANDRIAMIFIDISOA Ramamonjy∗ LALASOA Rufine Marius†

arXiv:2610.26642v1 [cs.CR] 19 Oct 2026

University of Antananarivo, Madagascar

October 20, 2026

Abstract We revisit DM-RSA [1], an RSA variant that uses two independent moduli, whose original version was broken by Håstad’s attack and contained an incorrect compromise-tolerance claim. We give a formal treatment of its repaired variant, DM-RSA-OAEP: (i) a complete IND-CCA2 security proof in the random-oracle model via a two-step hybrid argument, upper-bounding the security of the scheme by that of the weaker underlying RSA-OAEP instance, with an explicit simulation loss qD · 2−h ; (ii) a fault-detection theorem in an explicit adversary model that covers computation, key, and verification faults, including safe-error attacks in the sense of Yen–Joye [15], under a clearly stated physical-diversity assumption; (iii) an explicit analysis of why the countermeasure degrades to uselessness when the diversity assumption is violated (common-mode faults on a single chip). We position the scheme against the countermeasure landscape (Vigilant [13], Shamir [10], infective countermeasures [2]) and against the broken dual-modulus literature [11, 9, 12]. The contribution is deliberately framed as a fault countermeasure with a provable detection guarantee, not as a computationally stronger RSA. We conclude with a concrete instantiation (h = 256) and a detailed measurement protocol.

Keywords: RSA, OAEP, fault attacks, safe-errors, formal security proofs, dual-modulus cryptography, physical diversity.

1

Introduction

The RSA cryptosystem is vulnerable to side-channel attacks [7] and fault-injection attacks [4]. The standard countermeasure for CRT-RSA verifies the result of decryption by re-exponentiation [13]. Alternative approaches include Shamir’s countermeasure [10], whose original form was shown breakable by Wagner [14], and infective countermeasures [2], whose correctness is notoriously delicate. A recurring weakness of all single-device countermeasures is common-mode failure: the verification mechanism shares the silicon, the power supply, and the clock of the device it protects, so a single global disturbance (e.g., a power glitch) may corrupt both the computation and its verification. The original version of DM-RSA [1] used two moduli and recombined the plaintext by CRT; it was broken: (i) raw encryption is vulnerable to Håstad’s broadcast attack [6]; (ii) its compromisetolerance claim is false (factoring N1 suffices to recover m whenever z < N1 ); (iii) its numerical example is faulty (657 mod 5141 = 787, not 2979). The broader dual-modulus literature confirms ∗ †

ramamonjy.andriamifidisoa@univ-antananarivo.mg larissamarius.lm@gmail.com

1

this fragility: Sun et al. [11] identified weak parameter regions of Dual RSA, subsequently cryptanalyzed by Sarkar and Maitra [9]; Susanti et al. [12] recovered plaintexts of dual-modulus RSA without the private key via the e-th root attack. The lesson is consistent: structural redundancy without proper randomized padding adds no computational security. This work. We give DM-RSA’s repaired variant, DM-RSA-OAEP, the formal treatment required for a security audience: (i) a complete IND-CCA2 proof (Theorem 1) with an explicit hybrid argument and simulation loss, rather than a sketch; (ii) a formal fault-adversary model (Section 3) covering computation, key, and verification faults — the class that defeats most published countermeasures; (iii) a detection theorem (Theorem 2) covering single-fault adversaries, including safe-error strategies à la Yen–Joye [15], under an explicit physical-diversity assumption (Assumption 1); (iv) an explicit negative result (Theorem 3) showing that the guarantee vanishes when both moduli share a single chip — the honest boundary of the countermeasure; (v) a comparison against the full countermeasure landscape (Section 9) and a concrete instantiation with quantitative detection probabilities (Section 7). Design philosophy. The scheme does not claim computational gains. Its value is a detection guarantee with a provable bound that holds even when the verification logic itself is faulted, provided the two moduli live on physically independent units. To our knowledge, no published single-device RSA countermeasure offers a comparable guarantee against verification-fault adversaries; the price is a 4× decryption overhead and doubled key/ciphertext sizes.

2

Preliminaries and definitions

2.1

Notation

Let λ be the security parameter, h the hash-output length, and k the public exponent. For i ∈ {1, 2}, Ni = pi qi are independent λ-bit moduli with gcd(N1 , N2 ) = 1, di = k −1 mod φ(Ni ). For a distribution X, x ← X denotes sampling. For a randomized algorithm M, m ← M(x) denotes its output on input x. Advind-cca2 (A) denotes the IND-CCA2 advantage of A against Π scheme Π.

2.2

RSA-OAEP

RSAES-OAEP [3, 8] encrypts m as z ← OAEP-Encode(m, L, |N |) then w ← z k mod N ; the decoder returns (m, ok ), where ok = 1 iff the h-bit consistency check passes. OAEP is IND-CCA2 secure in the random-oracle model under RSA [5]. Capacity: |m| ≤ |N | − 2h − 2.

2.3

Syntax of DM-RSA-OAEP

Definition 1 (Scheme). DM-RSA-OAEP is a public-key encryption scheme with ciphertext space ZN1 × ZN2 : • Enc(m): sample independent seeds r1 , r2 ; compute zi ← OAEP-Encode(m, L, ri , |Ni |) and wi ← zik mod Ni ; output (w1 , w2 ).

2

• Dec((w1 , w2 )): compute zi′ ← widi mod Ni and (mi , oki ) ← OAEP-Decodect (zi′ , L); compute a redundant double comparison eqa , eqb ← Cmp2 (m1 , m2 , ok1 , ok2 ); set ok ← ok1 ∧ ok2 ∧ eqa ∧ eqb ; after a fixed time budget, output m1 if ok = 1 and a single error symbol ⊥ otherwise. The correctness requirement is Dec(Enc(m)) = m with probability 1 over the seeds.

2.4

IND-CCA2 security

A receives the public key, queries Dec adaptively (except the challenge pair), receives the challenge encryption of one of two chosen messages, and outputs a guess. Adv is the standard advantage gap.

3

Formal fault-adversary model

Definition 2 (Fault classes). A fault event is a one-time perturbation, chosen by the adversary from exactly one class below, occurring during a single invocation of Dec: (F1) Computation fault: the value of some intermediate variable in one exponentiation is replaced. The faulty output zi′ is either non-directed (distributed according to a fixed, seedindependent distribution D with min-entropy ≥ log2 Ni − 2) or directed (chosen by the adversary). (F2) Key fault: a bit of di is flipped before one exponentiation. (F3) Verification fault: a single instruction among {ok1 , ok2 , eqa , eqb , ok} or the final branch is skipped, forced, or negated. The adversary may repeat invocations and faults across queries, but at most one fault per invocation, on at most one physical unit. Assumption 1 (Physical diversity). The two moduli are implemented on two physically independent units with separate power supplies, resets, and clocks. A single fault event of Definition 2 affects at most one unit, and a fault on one unit cannot change values stored or computed on the other. Out of scope: memory reads by the adversary, multiple simultaneous faults, and faults affecting both units (e.g., a global glitch that resets both devices at once). Remark 1. Assumption 1 is strong but implementable: dual-chip secure elements and HSM architectures with independent voltage domains satisfy it. It is the only assumption under which the scheme’s advantage over single-device countermeasures materializes; Theorem 3 quantifies the failure when it is violated. Definition 3 (Detection advantage). For a fault strategy F of Definition 2, let Undet(F ) be the probability (over all randomness) that Dec outputs a message that differs from the correctly decrypted one while signaling no error. The scheme detects F with probability 1 − Undet(F ).

3

4

The DM-RSA-OAEP cryptosystem

Algorithm 1 Dec((w1 , w2 )) with safe-error protection d

▷ unit 1 ▷ unit 2

1: z1′ ← w1 1 mod N1 d

2: z2′ ← w2 2 mod N2

3: (m1 , ok1 ) ← OAEP-Decodect (z1′ , L) 4: (m2 , ok2 ) ← OAEP-Decodect (z2′ , L)

▷ comparison, copy A ▷ independent copy B ▷ stored twice, complementary ▷ time-uniform rejection

5: eqa ← [m1 = m2 ∧ ok1 = ok2 ] 6: eqb ← [m1 = m2 ∧ ok1 = ok2 ] 7: ok ← ok1 ∧ ok2 ∧ eqa ∧ eqb

8: wait fixed time budget

9: if ok ̸= 1 on both copies then return ⊥ 10: end if 11: return m1

Critical implementation points. (i) Constant-time OAEP-Decode on both units. (ii) The double comparison eqa , eqb is computed by two instruction streams that do not share registers, so that a single verification fault cannot flip both. (iii) The flag ok is stored in two complementary encodings; the final branch accepts only if both agree on true. (iv) The error symbol, the response time, and the power profile are identical for every failure reason (decode failure on either unit, mismatch, verification fault) — otherwise the rejection pattern itself is a distinguishing oracle that voids Theorem 1 and enables safe-error strategies.

5

Security analysis

5.1

Computational security: complete proof

Theorem 1 (IND-CCA2 upper bound). Let A be an IND-CCA2 adversary against DM-RSAOAEP making at most qD decryption queries, qH hash queries, and qG MGF queries, with advantage ε. Let h be the OAEP consistency-check length. Then there exists an adversary B against RSA-OAEP (same parameters) in the random-oracle model with Advind-cca2 RSA-OAEP (B) ≥

ε − qD · 2−h , 2

with B making at most qD decryption, qH , and qG oracle queries, and running in time T (A) + O(qD · texp ), where texp is the cost of one exponentiation. Proof. We proceed in three games. Let Si be the event that the adversary wins in Game i. Game 0. The real IND-CCA2 experiment against DM-RSA-OAEP: Pr[S0 ] = 12 + ε. Game 1. The challenger picks a uniform bit b∗ ∈ {1, 2} and generates the moduli accordingly: for b∗ = 1, the left component of the challenge is answered by an external RSA-OAPE instance of modulus N1 = N ∗ , and (N2 , k, d2 ) is generated honestly (symmetrically for b∗ = 2). All hash and MGF oracles are simulated consistently for both sides. The decryption oracle is simulated: the internal side is computed directly; the external side is answered by querying the RSA-OAEP decryption oracle, which is admissible except when a query component equals the challenge ciphertext, in which case the query is rejected under the standard CCA2 rule. The two games are identically distributed from A’s view, so Pr[S1 ] = Pr[S0 ]. Game 2. As Game 1, but the simulated decryption rejects whenever the simulated side fails its OAEP consistency check, regardless of the external side. The only behavioral change occurs when a query (w1 , w2 ) has a simulated side that fails decoding but the full oracle would have accepted, i.e., the external side decodes correctly and the consistency check passes against 4

a wrongly decoded simulated side. For the output to be accepted, the faulty simulated side must pass the h-bit consistency check, which a randomly distributed faulty value does with probability at most 2−h . Over at most qD queries, Pr[S2 ] − Pr[S1 ] ≤ qD · 2−h . Deriving the reduction. In Game 2, A wins with probability Pr[S2 ] ≥ 21 + ε − qD 2−h , and its whole interaction with the external modulus is routed through the RSA-OAEP instance. B runs A with b∗ uniform: with probability 21 the challenge side A attacks is the external one, in which case B perfectly inherits A’s winning strategy. Hence ε − qD · 2−h . 2 Remark 2. Theorem 1 is a deliberate negative result: it upper-bounds the scheme’s security by that of standard RSA-OAEP and makes explicit that structural duality buys no computational security. The scheme’s value is exclusively in Theorem 2. Adv(B) ≥

5.2

Fault detection: main theorem

Theorem 2 (Single-fault detection). Under Assumption 1, for every adversary restricted to non-directed faults of classes (F1) and (F2) of Definition 2, Undet ≤ 2−h . For every adversary restricted to a single directed fault of classes (F1)–(F3) that does not already know the plaintext of a valid challenge, Undet ≤ 2−h + δ, where δ is the probability that the adversary forges a pair (z1′ , m′1 ) passing OAEP-Decode on the faulty unit and matching the honest ′ ′ m2 ; δ ≤ Advind-cca2 RSA-OAEP (B ) for the reduction B of Theorem 1, hence δ is negligible. Proof. Non-directed faults. Suppose the fault hits unit 1 (the case of unit 2 is symmetric). Unit 2 outputs the correct (m2 , ok2 = 1). A faulty acceptance requires z1′ ̸= z1 to pass the h-bit OAEP consistency check and the decoded m′1 to satisfy m′1 = m2 . By (F1)–(F2), z1′ has min-entropy at least log2 N1 − 2, so the consistency check passes with probability at most 4 · 2−h ; the subsequent equality test only rejects more. A union bound over the two units yields the claim (up to the constant, absorbed by parameter choice h = 256). Information- and timeuniform rejection (Algorithm 1) ensures the rejection event leaks nothing beyond one bit, which is independent of z1′ ’s value by the uniformity of rejection. Verification faults (F3). The acceptance predicate requires the conjunction ok1 ∧ ok2 ∧ eqa ∧ eqb evaluated consistently on two complementary stored copies. A single fault on one comparison, one flag, or the final branch flips at most one of the four conjuncts or one of the two stored copies; in every case at least one remaining copy forces rejection, and the output is ⊥, not a wrong plaintext. Hence (F3) faults cause denial of service, never faulty acceptance: Undet = 0 for class (F3) alone. Directed faults. A directed fault that produces a valid-looking z1′ whose decoding m′1 matches the honest m2 constitutes precisely a successful prediction of the plaintext of a ciphertext under N1 ’s RSA-OAEP instance, or a forgery passing its consistency check with a correct plaintext relation. The reduction B ′ embeds its challenge as w1 and uses the adversary’s directed fault to answer it, gaining advantage δ. By Theorem 1 and the IND-CCA2 security of RSA-OAEP [5], δ is negligible. Remark 3 (Safe-errors). The Yen–Joye safe-error strategy [15] targets precisely the verification predicate: the adversary faults an instruction and reads the single accept/reject bit to learn whether that instruction was control-flow-critical. Against Algorithm 1, this bit is uniform over all failure reasons (uniform rejection), so the bit carries no information about which instruction was hit — the safe-error channel is closed. Moreover, converting a safe-error into a faulty acceptance requires flipping both comparison copies on two independent units, violating Assumption 1. 5

5.3

Common-mode failure: the honest boundary

Theorem 3 (Single-chip degradation). If Assumption 1 is violated — both moduli computed on a single unit sharing power and clock — there exists a simple two-fault adversary of class (F3) with Undet = 1: skip both eqa and the ok conjunction, forcing acceptance of a directed faulty m′1 . Proof. With both moduli on one chip, the adversary may inject two verification faults in one invocation (Definition 2 restricted to one unit no longer applies). Forcing ok1 ← 1 and eqa ← 1 leaves the acceptance predicate true, and the output is the faulty m′1 ; hence detection fails completely. Remark 4. Theorem 3 is stated deliberately: it shows that the guarantee is architectural, not algorithmic. Reviewers and practitioners must read DM-RSA-OAEP as a countermeasure for dual-chip deployments only. On a single chip, Vigilant’s re-exponentiation [13] is strictly preferable (cost ∼ 1/10 decryption vs. ∼ 4×).

6

Cost analysis

Decryption cost Relative cost Ciphertext size Detect. prob. (single fault) Robust to verification faults Requires physical diversity

RSA-2048

CRT + Vigilant

Shamir (fixed)

Infective [2]

DM-RSA-OAEP

(d) 1 E2048

(d) 2 E1024 + re-exp.

(d) 2 E1024 + checks

(d) 2 E1024 + rand.

1× 2048 b none — —

∼ 0.35× 2048 b 1 − 1/p no no

∼ 0.3× 2048 b 1 (if checks hold) no no

∼ 0.3× 2048 b heuristic partially no

2 E2048 ∼ 4× 4096 b 1 − 2−h provable yes (Thm. 2) yes (Thm. 3)

(d)

Table 1: Countermeasure landscape. DM-RSA-OAEP is the only entry with a provable detection bound against verification-fault adversaries, and the only one requiring dual-chip deployment.

7

Concrete instantiation and quantitative guarantees

With SHA-256 as the hash and MGF1-SHA-256 as the mask generator (h = 256, per RFC 8017 [8]) and 2048-bit moduli: • Detection guarantee: single non-directed fault undetected with probability ≤ 2−256 ≈ 10−77 per invocation — eleven orders of magnitude below Vigilant’s 1/p ≈ 2−1024 only if p is uniform; in practice Vigilant’s guarantee is 1 − 1/p ≈ 1, but it holds only if the verification exponentiation itself is fault-free, which DM-RSA-OAEP does not need to assume. • Capacity: |m| ≤ 2048 − 512 − 2 = 1534 bits per modulus. • Keys: two independent 2048-bit moduli generated by a certified RNG on separate dies at provisioning time. • Verification schedule: the two decryption streams run concurrently; the consistency check runs only after both complete; the fixed time budget equals the maximum over all failure paths.

8

Preliminary evaluation and measurement protocol

Disclaimer. The figures below are simulated estimates derived from published OpenSSL benchmarks and known cost models of modular arithmetic; they identify orders of magnitude 6

and the critical points to measure. Real measurements on an embedded platform with fault injection are mandatory before deployment and are the subject of ongoing work.

8.1

Simulated estimates (x86-64, OpenSSL 3.x)

Based on public benchmarks (RSA-2048: encryption ≈ 0.05 ms, CRT decryption ≈ 1.5 ms on a modern core) and a cubic-cost model for large-exponent exponentiation (2048-bit ≈ 4× 1024-bit): Operation

RSA-2048

CRT + Vigilant

DM-RSA-OAEP

Encryption (est.) Decryption (est.) Relative decryption

∼ 0.05 ms ∼ 5 ms 3.2×

∼ 0.05 ms ∼ 1.55 ms 1×

∼ 0.10 ms ∼ 6 ms ∼ 4×

Table 2: Simulated timings. To be replaced by real measurements.

8.2

Measurement protocol (reproducible)

• Platforms: (a) x86-64, OpenSSL 3.x; (b) STM32F4 (Cortex-M4), mbedTLS; (c) dualchip setup: two STM32F4 on separate supplies, UART-locked; (d) FPGA Artix-7, two RSA cores. • Metrics: median and 99th-percentile latency (10,000 runs, Welch’s t-test on log-timings), rejection latency distribution, energy (oscilloscope on shunt). • Fault injection: clock/voltage glitching and laser (near-IR, backside if available) on one unit at a time; success criterion = faulty acceptance; report detection rate with 95% confidence intervals (Wilson). • Baselines: Vigilant on a single chip; Shamir (corrected); DM-RSA-OAEP dual-chip; DMRSA-OAEP forced on a single chip to validate Theorem 3 empirically.

8.3

Statistical plan

Detection rates are estimated over ≥ 1,000 successful fault injections per class (F1)–(F3) and reported with Wilson 95% intervals; latencies with trimmed means. Code, board files, and raw traces will be released for artifact evaluation.

9

Related work

CRT-RSA countermeasures. Bellcore-style faults [4] motivated three families: (i) verification by re-exponentiation [13], effective but itself faultable in the verification step; (ii) Shamir’s countermeasure [10], whose original form falls to Wagner’s attack [14]; (iii) infective schemes [2], whose correctness proofs are delicate and which leak through timing in several published instances. All share one silicon with the computation they protect; DM-RSA-OAEP trades a 4× cost for independence of the verification from the faulted unit. Dual RSA and its cryptanalysis. Sun et al. [11] proposed Dual RSA (two exponent–modulus pairs sharing key material) and identified weak parameter regions; Sarkar and Maitra [9] broke a significant claimed-secure region. Susanti et al. [12] recovered dual-modulus plaintexts without the private key via the e-th root attack, confirming that duality without randomized padding adds nothing. The original DM-RSA [1] falls in the same class (broken here and by [6, 12]); DM-RSAOAEP repairs it and, unlike all of the above, targets fault detection rather than computational novelty. 7

Safe-errors. Yen and Joye [15] showed that “verify before output” leaks whether the faulted instruction was on the critical path, converting countermeasures into oracles. Our double comparison with complementary-stored flags and uniform rejection closes this channel within the single-fault model (Theorem 2).

10

Discussion, limitations, and conclusion

Limitations. (1) The detection guarantee holds only in the single-fault model; a two-fault adversary on a single chip breaks the scheme (Theorem 3). (2) Assumption 1 is architectural and must be audited per deployment. (3) No real measurements yet; Section 8 is a protocol, not a result. (4) The 4× decryption cost and doubled sizes limit applicability to high-value, low-throughput operations (root-key operations, HSM commands). Conclusion. We gave DM-RSA-OAEP a complete formal treatment: a full IND-CCA2 hybrid proof upper-bounding its computational security by RSA-OAEP (Theorem 1); a detection theorem covering computation, key, and verification faults, including safe-error strategies (Theorem 2); and an explicit common-mode negative result (Theorem 3) delimiting the guarantee to physically diverse deployments. The scheme is positioned honestly in the countermeasure landscape: it is the only construction with a provable detection bound against verification-fault adversaries, at a 4× cost. Ongoing work includes the dual-chip fault-injection campaign of Section 8 and an extension of the model to multi-fault adversaries with resource-bounded fault budgets.

References [1] A. Ramamonjy, L. R. Marius, DM-RSA: An Extension of RSA with Dual Modulus, arXiv:2507.14197, 2025. [2] A. Barenghi, L. Breveglieri, I. Koren, D. Naccache, Fault Injection Attacks on Cryptosystems: Theoretical Models, Practical Experiments and Countermeasures, ACM Computing Surveys, 45(2), Article 6, 2013. [3] M. Bellare, P. Rogaway, Optimal Asymmetric Encryption, EUROCRYPT ’94, LNCS 950, pp. 92–111, 1995. [4] D. Boneh, R. A. DeMillo, R. J. Lipton, On the Importance of Checking Cryptographic Protocols for Faults, EUROCRYPT ’97, LNCS 1233, pp. 37–51, 1997. [5] E. Fujisaki, T. Okamoto, D. Pointcheval, J. Stern, RSA-OAEP Is Secure under the RSA Assumption, J. Cryptology, 17(2):81–104, 2004. [6] J. Håstad, Solving Simultaneous Modular Equations of Low Degree, SIAM J. Comput., 17(2):336–341, 1988. [7] P. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, CRYPTO ’96, LNCS 1109, pp. 104–113, 1996. [8] K. Moriarty et al., PKCS #1: RSA Cryptography Specifications Version 2.2, RFC 8017, IETF, 2016. [9] S. Sarkar, S. Maitra, Cryptanalysis of Dual RSA, Designs, Codes and Cryptography, 82(1– 2):431–457, 2017.

8

[10] A. Shamir, Method and Apparatus for Protecting Public Key Schemes from Channel and Fault Attacks, US Patent 5,991,415, 1999. [11] H.-M. Sun, M.-E. Wu, W.-C. Ting, M. J. Hinek, Dual RSA and Its Security Analysis, IEEE Transactions on Information Theory, 53(8):2922–2933, 2007. [12] B. H. Susanti, T. K. Silim, N. P. R. Adiati, M. W. Ardyani, eth Root Attack on Dual Modulus RSA, ZERO: Jurnal Sains, Matematika dan Terapan, vol. 9, no. 1, 2025. [13] D. Vigilant, RSA with CRT: A New Cost-Effective Solution to Thwart Fault Attacks, CHES 2008, LNCS 5154, pp. 130–145, 2008. [14] D. Wagner, Cryptanalysis of a Provable Secure CRT-RSA Algorithm, CRYPTO 2004, Rump Session. [15] S.-M. Yen, M. Joye, Checking Before Output May Not Be Enough Against Fault-Based Cryptanalysis, IEEE Transactions on Computers, 49(9):967–970, 2000.

9

Related documents

• Fault attacks on two software countermeasures#322391
• CVE-2026-93283#1091812
• Toward Principled LLM Safety Testing: Solving the Jailbreak Oracle Problem#163158
• CVE-2026-89946#989150
• CVE-2026-97574#1098292