ElGamal - Breaking Smart Card Based ElGamal Signature and Its Variants - Attack Model

Sep 18, 2026

The slides analyze how smart-card tamperproof hardware faults can be exploited to compromise cryptographic secret keys, focusing on breaking smart card based ElGamal signatures and their variants. They outline an attacker model that introduces physical faults such as heat, laser, pressure, or radiation, then explains resulting exposure of secrets including DES/RSA keys and authentication data. Mathematical signing components for ElGamal are presented along with an attack idea that predicts the signature generation randomness by manipulating PRG behavior.

LanguageEnglish

CategoryTechnology

FormatPDF

Pages21

Reading Time53 min

AccessFree to download

ElGamal Signature

Signature structure and related keys

Exploiting hardware faults

The Attack Model

Idea for finding x_a via PRG manipulation

Main idea for collecting (r,s) output

ElGamal Signature Card Breaking Smart Card Based ElGamal Signature and Its Variants Asiacrypt96 Rump Session, 5 Nov. 1996 Yuliang Zheng Monash University Tsutomu Matsumoto Yokohama Nat. University © Yuliang Zheng, 1996 1 Exploiting hardware faults n Secret key algorithms 􀀀 DES, IDEA, FEAL, etc- - -broken by Biham & Shamir (18 Oct. & 30 Oct.) 􀀀 (see also J-J Quisquater, 23 Oct.) n Public key signature 􀀀 RSA- - -broken by lBellcore (25 Sept., no details were published) lNat. Uni. of Singapore (23 Oct.) 􀀀 ElGamal family-- ??? © Yuliang Zheng, 1996 2 Completing the big picture n We show how to break smart card based 􀀀 ElGamal signature and 􀀀 all its variants, by (temporally) falsifying part of the circuitry in the smart card n Time: 31 Oct. 1996 © Yuliang Zheng, 1996 3 The Attack Model nAn attacker, who is in possession of a target smart card, may introduce faults into tamperproof hardware in the smart card, say by exposing it to certain physical effects (heat, laser, pressure, radiation, etc) © Yuliang Zheng, 1996 4 The Attack Model (cnt’d) n The attack may then compromise a secret in the smart card. 􀀀 a DES encryption / decryption key 􀀀 a RSA signature-generation / decryption key 􀀀 certain authentication / identification cards 􀀀 …... © Yuliang Zheng, 1996 5 ElGamal Signature n Alice’s keys 􀀀 xa ---secret key for signature generation 􀀀 ya = gx a modp - - -public key n Alice’s signature on a message m is a pair of number (r,s): 􀀀 x ∈R [1,…, p − 1] r = gx mod p 􀀀 s = hash~~ ~~(~~ ~~mx)~~ ~~−~~ ~~xa~~ ~~⋅~~ ~~r~~ ~~ mod(p − 1) © Yuliang Zheng, 1996 6 Idea for finding xa nAn attacker may figure out xa by making the “random” number x predictable, through the falsification of part of the hardware 􀀀 software pseudo-random number generator- - -suppressing the contents of the status register that stores the current “seed” number 􀀀 hard pseudo-random number generator- - -suppressing its output © Yuliang Zheng, 1996 7 Two possibilities n software pseudo-random number generator 􀀀 suppressing the contents of the status register that stores the current “seed” number nhard pseudo-random number generator 􀀀 suppressing its output © Yuliang Zheng, 1996 8 When software PRG is used m r,s © Yuliang Zheng, 1996 9 Main idea n suppress the contents of the status register that stores the current seed for the PRG n so that only a fixed number, such as the all-1 value, is (temporarily) available to the CPU n collect the output (r,s ) of the smart card © Yuliang Zheng, 1996 10

FAQs

How can an attacker introduce faults into a smart card?

The attacker uses physical effects such as heat, laser, pressure, or radiation to compromise tamperproof hardware inside the smart card.

Which secret information can the fault attack compromise?

The slides indicate compromise of secret encryption/signature keys (e.g., DES or RSA key material) and certain authentication/identification cards.

How does the attack idea help an attacker find x_a in ElGamal signatures?

By making the PRG “random” number predictable through falsification of hardware, suppressing internal seed or PRG outputs so the randomness used in signature generation becomes constrained.

Sep 18, 2026

Upload by Alex Sinclair