Digital Signature Schemes and Security Issues
Explore asymmetric techniques in digital signatures with PK encryption, focusing on the RSA signature scheme and Rabin signatures. Learn about the implementation, setup, generation, and verification processes along with security issues such as Active attacks and Existential forgery.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CIS 5371 Cryptography 9. Data Integrity Techniques 1
Asymmetric techniques, I Digital signatures With PK encryption, Alice can use her private key to decrypt a message and the resultant ciphertext can be encrypted to recover the message. This ciphertext can serve as a Manipulation Detection Code (MDC). The verification of a MDC can be performed by anyone since the public key is available to anyone.
Example of an MDC based on RSA Let p = 101, q = 113. Then n = 11413. (n) = 100 112 = 11200 = 26527 Alice takes e = 3533, d = 6597, with ?? 1 ??? (?). Alice publishes: n = 11413, e = 3533. Let the message be m = 5761 Alice computes the MDC: 57616597 (mod 11413) = 9726 Suppose Bob wants to verify that 9726 is the MDC of Alice Bob computes 97263533 mod 11413 = 5761
Digital signature schemes M, message space S, signature space K, signing key space K , verifying key space Gen: 1? K K , an efficient key generating algorithm Sign: M K S, an efficient signing algorithm Verify: M S K {true,false} an efficient verifying algorithm.
The RSA signature scheme Signature setup: N = pq, where p and q are primes. M= S= ZN , with keyspace K = {(N,e,d) : ?? = 1 ????(?). Public key = (N,e), Private key (N,d). Signature generation:for m Zn, ? = ????? = ?? ???? Signature Verification ???????,? ?,? = ???? iff ??= ? ????
Security issues for Digital Signatures Active attacks digital signatures Adaptive Chosen-Message Attack (CMA): The attacker chooses adaptively a number of messages and obtains the corresponding signatures: the task of the attacker is successful if he can sign a (new) target message. Existential forgery under CMA: The adversary can compute one (new) message and its signature. With RSA the algorithms (Sign,Verify) form a one-way trapdoor pair. This means that it is easy to compute valid message-signature pairs (by first selecting a signature and then finding the corresponding message). However, computing message-signature pairs should be hard. A usual way to prevent this is add redundancy to the message.
Rabin signatures Signature setup: Same as RSA Public key = (N,b), Private key = (p,q). Signature generation: Exercise Signature Verification: Exercise
The ElGamal signature scheme Signature setup Same as ElGamal encryption scheme, ? and ?-bit prime, ?a generator of ?? M= {0,1}?, S= ?? and ? = ????? ?: ?? 1, and keyspace K = ?? 1. Public key = (p, g, y) Private key = (p, g, x).
The ElGamal signature scheme Signing Let ? be a message. For public key (p,g,y), with y = gx modp, and a secret random exponent k ?? 1, define: ?????,? = ?,? , where ? = ?? ??? ? ? = ?(?) ?? ? 1???(? 1) Verification Verify(p,g,y)(?,(?,?)) = true iff 0 < ? < ? 1,0 < ? < ?and st ys = ??(?)mod p
Toy example Let p = 467, g = 2, x = 127, y = 132 message m = 100, Choose k = 213. Then k-1 mod 466 = 431. The signature is: s = 2213 mod 467 = 29 t = ? ?? ? 1???(? 1) = 100 127 29 431 ??? 466 = 51 Verification: 2100 ? 2951 13229 mod 467
The security of ElGamal signatures If the DL problem is feasible then ElGamal signatures can be forged. The converse may not be true. The exponent k must be private cannot be used twice best: chosen at random.
The Digital Signature Algorithm (DSA) Let p be a an L-bit prime, 512 L 1024 and L 0 mod 64 , let ? be a 160-bit prime that divides? 1 and let? ? ?? ( is a generator of order ?) Let M = ?? 1, S = ?? ??and K = { ?,?, ,?,? : ? = ????? ?}. The public key is (?,?,?,?). The private key is (?,?,?,?). be a ?-th root of 1 mod p .
The Digital Signature scheme Signing Let m be a message. For public key (p,g, ,y), with y = x mod p, and secret random number k Zp-1, define: ?????,? = (?,?), where s = (??????) ???? ? = ? ? + ?? ? 1???? where H is an appropriate cryptographic hash function. Verification Let e1 = (?(m)) t -1modq e2 = s t -1modq ??????(?,?,?,?)(m,(s,t)) = true ( e1ye2 modp) modq = s.
Provable security Forging signatures We must how that given a message it is hard to forge a signature. Is this enough? There are several attacks we already discussed: Existential forgery Adaptive Chosen-Message Attacks What is really needed is a formal security model for digital signatures, that allows for all possible threat scenarios and all protocol aspects. One such model is the Random Oracle model.
One-time signatures Lamport signature scheme Let k be an integer, P = {0,1}k. Suppose that f : Y Z is a one-way function, and A = Y k. Let yi,j Y be chosen at random, 1 i k, j =0,1, and zi,j =f (yi,j), Let K consist of the 2k pairs : (yi,j, zi,j). The y s are the private key, the z s the pubic key.
Lamport signature scheme Signing Let x = (x1,x2, xk) P be a message. For K = (yi,j, zi,j) define sigK(x1,x2, xk) = (y1x1,y2x2, , ykxk) . Verification verK((x1,x2, xk),(y1x1,y2x2, , ykxk)) = true f(yi) = zixi ,1 i k
The security of the Lamport signature scheme The security of the Lamport signature scheme can be proven if we assume that: The one-way function is bijective, and that The public key consists of distinct elements.
