DSA — Digital Signature Algorithm
AQSh davlat imzo standarti. 1991 yilda NIST tomonidan taklif qilingan (U.S. Patent 5231668), aslida NSA yaratgan. U ma'lumotni shifrlash uchun emas, faqat raqamli imzo uchun. SHA xesh-funksiyasi bilan birga DSS (Digital Signature Standard) ni tashkil etadi.
Parametrlar
- p — katta tub son (512–1024 bit, uzunligi 64 ga karrali; hozir 2048–3072 bit tavsiya etiladi).
- q — 160 bitli tub son, p−1 ning bo'luvchisi.
- h < p−1 natural son, h(p−1)/q mod p > 1.
- g = h(p−1)/q mod p.
- Yopiq kalit: x < q.
- Ochiq kalit: y = gx mod p.
(p, q, g) foydalanuvchilar guruhi uchun umumiy bo'lishi mumkin; y — ochiq, x — yopiq.
r = (gk mod p) mod q
s = k⁻¹·(H(m) + x·r) mod q
u₁ = H(m)·w mod q, u₂ = r·w mod q
v = (gu₁·yu₂ mod p) mod q
v = r bo'lsa — imzo haqiqiy
Mashq 1: p = 83, q = 41, h = 13, x = 12, k = 5, H(m) = 7. g = 13² mod 83 = 3, y = 3¹² mod 83 = 75, r = (3⁵ mod 83) mod 41 = 77 mod 41 = 36, s = 5⁻¹·(7 + 12·36) mod 41 = 14 → (r, s) = (36, 14).
«Imzo qo'yish» tugmasi g, y, r, s maydonlarini avtomatik to'ldiradi. So'ng «Imzoni tekshirish»ni bosing — ✓ chiqadi. Endi H(m) ni o'zgartirib (go'yo hujjat o'zgargandek) yana tekshiring — imzo qalbaki bo'lib qoladi. r va s maydonlariga vergul bilan bir nechta nomzod kiritib, qaysi biri haqiqiy ekanini aniqlash mumkin.
Ikki xil xabar bir xil k bilan imzolansa, yopiq kalit x ni oddiy algebra bilan topish mumkin. 2010 yilda Sony PlayStation 3 ning imzo kaliti aynan shu xato (har doim bir xil k) tufayli fosh bo'lgan.