Special Topics CS 4803
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4803 at Georgia Institute of Technology - Main Campus taught by Ashwin Ram in Fall. Since its upload, it has received 16 views. For similar materials see /class/234007/cs-4803-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Special Topics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 11/02/15
CS 4803 Computer and Network Security Alexandra Sasha Boldyr eva Digital signatures Digital signature schemes 0 Let s study the problem of data authentication and integrity in the asymmetric publickey setting 0 A sender needs to be assured that a message came from the legitimate sender and was not modified on the way 0 MACs solved this problem but for the symmetrickey setting 0 A digital signature scheme primitive is the solution to the goal of authenticity in the asymmetric setting Digital signature schemes DSKS gVWF k k 9 p s MsgSppk message space pks t Sks M5 0 o1o39 M M Sender S Receiver It is required that for every MeMsgSp every pksk that can be output by K if 039 is output by sagw then VFpkMO39l Digital signature schemes 0 The signing algorithm can be randomized or stateful but it does not have to be The MsgSp is often 01 for every pk 0 Note that the key usage in a digital signature scheme is reverse compared to an asymmetric encryption scheme in a digital signature scheme the holder of the secret key is a sender and anyone can veri y o in an asymmetric encryption scheme the holder of the secret key is a receiver and anyone can encrypt Security definition for digital signatures Fix DSKSignVF Run Kto get pksk For an adversary A consider an experiment Expggmam Return 1 iff VFpkMo1 and MeMsgSppk that was was not queried to the signing oracle The ufcma advantage of A is defined as Adv g mawj Pr Expggma A signature scheme is ufcma secure if no efficient adversary has non negligible uf cma advantage A 1 l Plain RSA signature scheme Algorithm Kk ltltNegtltNpqdgtgt i Kirk Retum NeNpqd WM M Algorithm VFN EM z 5 then return L If M Z or z Z then return 0 z lt M mod N If M IE mod N then return 1 else return 0 Return 1 Algorithm SignN M o Is Plain RSA signature scheme secure Plain RSA is not secure Forger FZSignN p dgtgtNe zezg MezemodN Return Mm Forger FISignN p ANN 6 Return 11 Forger ngignNieCNNm M1 amp Z3 7 1M M2 e MMI mod N 001 H SignNEM1 002 H SignNEM2 z E Z1Z2 mod N Return Mz All adversaries forgers have uf cma advantages 1 and are effiCIent Hashtheninvert paradigm 0 We want to have an RSAbased signature scheme that resists the attacks above 0 has a more flexible message space 0 provany secure 0 An idea let s hash the message first FullDomainHash FDH RSA signature scheme 0 Let H 01HZ be a hash function 0 FDHRSA is a signature scheme D5 Krsa7Sign7VF Algorithm Signg gq AM Algorithm VFgS M7z y e HM y e H M zeydmodN yezemodzv Return I If y y then return 1 else return 0 What properties of the hash function do we need If we have hash that destroys the algebraic structure and is collision resistant the obvious attacks do not apply However to prove security we need more 0 we need to assume that the hash function is a random function this is not a very realistic assumption Theorem Under the RSA assumption the FDHRSA signature scheme is ufcma secure in the random oracle RC model In practice RSA PKSC1 Fix a function Hash0lv01n where n2128 o Eg for SHAl nl60 0 Define PKCSHASHM as PKCSHASHM I 00 01 ff39ff ffO O IHashIDI H I k If Hash is collision resistant so is PKCSHASH But hardness of computing the inverse of the RSA function on a random point in 23 does not imply that on a point in SPKCSHASHM Me0l The are no attacks known but it does not mean we should not be concerned Other signature schemes 0 Let s consider several signature schemes whose security relies on the hardness of the DL problem 0 Schnorr signature scheme Algoritm Kk pick a kbit prime p st p2q1 pick geZlquotJ of order q x kaq ngx Pick a hash function H0lquotgtZq Return HgpqXHygyqulel Algoritm SignskM s kaq Ykgy mod p ckHMl lY skycgtlt mod q Return Ys Algoritm VFpkMYS ckHMllY If gSYgtltc mod p th en return 1 else return 0 Security of Schnorr and EIGamaI signatures o The Schnorr and ElGamal signature schemes are uf cma secure in the random oracle RC model in groups where the discrete logarithm DL problem is hard Other signature schemes 0 ElGamal signature scheme Algoritm Kk pick a kbit prime p pick a generator 9 of 2 3 kap71 gtlt Picka hash function H0lquotgtZpi1 Return HgpqXHygyqulel Algoritm SignskM VFZF H Ykgy mod p ssv 1 HMl mew mod p71 Return Ys Algoritm VFpkMYS If XYYSgHMllYl mod p then return 1 else return 0 Sig nature schemes variations 0 Multisignatures several signers create a signature on a single message that is shorter and faster to verify than when a standard signature scheme is used in a straightforward way 0 Aggregate signatures similar to multisignatures but the signers sign different messages 0 Threshold signatures a group of n users holds a single public key Each user holds a share of the secret key At least t users need to cooperate to produce a valid signature on a message 0 Proxy signatures a signer delegates its signing capabilities to
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'