除數字領域外,證明某個人的確生成了某個消息的屬性至關重要。在我們現實生活中,這主要是顺利获得紙上手寫的簽名來實現的。例如,如果我們簽訂一份合同或簽署個訂單,收到合同或訂單的人就可以向法官證明,我們的確對這個消息進行了簽名(當然,有人也可能偽造簽名:但也存在不少法律和道德障礙防止大多數人這樣做的企圖)。與傳統手寫簽名一樣,只有創建數字消息的人才能生成有效的簽名。為了使用密碼學本原元達到這個目的,我們只能使用公鑰密碼學,其基本思想為:對消息簽名的一方使用私鑰,接收方則使用對應的公鑰。

設Bob的私鑰是保密的,只有他本人才能對消息x進行簽名。為了將一個簽名與一個消息對應,x也必須是數字簽名的一個輸入。Bob在對消息進行簽名後,將得到的簽名s附加到消息x之後,並將得到的(x,s)對發送給 Alice。請注意:數字簽名本身是沒有任何意義,除非與消息一起使用。沒有消息的數字簽名相當於沒有對應合同或訂單的手寫簽名。

數字簽名本身僅僅是一個(大)整數,比如一個2048位長的字符串。只有在驗證簽名是否有效時,此簽名對她而言才有用。因此,我們也需要一個輸入為x和簽名s的驗證函數。為了將此簽名與Bob掛上關係,此驗證函數還需要Bob的公鑰。儘管驗證函數的輸入很長,但其輸出卻非常簡單,就是二進制語句“真”或“假”。如果x的確是使用公開驗證密鑰對應的私鑰簽名的,則輸出為真,否則為假。

顺利获得上面這些綜合觀察, 數字簽名的核心屬性為:被簽名的消息可以明確地追蹤到它的發起人,因為只有唯一的簽名者的私鑰才能計算出有效的簽名。只有簽名者自己才能生成一個簽名,因此可以證明:簽名方的確生成了這個消息。這樣的證明甚至具有法律上的意義,比如美國的國際和國內商業行為的電子簽名( ESIGN)法案,德國的簽名法等。大家可能已經注意到,上面的基本協議沒有為消息给予任何保密性,因為消息x是以明文形式發送的。當然,也可以使用類似AES或3DES的算法對其進行加密,進而保證其保密性三種主流的公鑰算法家族,即整數因式分解、離散對數和橢圓曲線,都可以用來構建數字簽名。