Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have finally managed to verify some simple PGP signed message blocks. However, I discovered that for some reason, my implementation limits me to verifying data that is 9-16 bytes long. no less. no more.

is there some instruction somewhere (RFC4880 or elsewhere) that specifies how to deal with plaintext data of any length? maybe there is some sort of padding i missed? pkcs1?

I am pretty sure i formatted the data to hash properly, since the instructions in RFC 4880 sec 5.2.4 say for text documents, just replace all \n with \r\n and add a trailer. since my test values were single lines of data, nothing had to be replaced

all of these values are in base 10 unless otherwise noted:

// DSA public key values
p = 175466718616740411615640156350265486163809613514213656685227237159351776260193236923030228927905671867677337184318134702903960237546408302010360724274436019639502405323187799029742776686067449287558904042137172927936686590837020160292525250748155580652384740664931255981772117478967314777932252547256795892071
q = 809260232002608708872165272150356204306578772713
g = 127751900783328740354741342100721884490035793278553520238434722215554870393020469115393573782393994875216405838455564598493958342322790638050051759023658096740912555025710033120777570527002197424160086000659457154926758682221072408093235236853997248304424303705425567765059722098677806247252106481642577996274
y = 172935968966072909036304664996424500241381878537444332146572958203083745609400290814117451480512268901233962890933482206538294509037615827035398352528065134903071886710296983781453184598843331365336270501467458073523376152406987560592548479865116940266729198119357206749848310472131186772143408998928864559411

not working:

Hash: SHA1

Version: BCPG v1.39


data hashed (in hex): 6162636404011102001b05024fed076f141c616263203c6d616b636d406161612e636f6d3e04ff00000021

r = 666804200764671083282351405489424949903645052927
s = 558743769080942454889260816818443017172325925608

w =  702955297882281869313155599553522395227576660460 // s^-1 mod q
u1 = 190417717173929082607343542521304347388874234334
u2 = 306786785479358548892951170619047936651163362761
v = g^u1 * y^u2 % p % q = 737052148656331043521702886300418501784667890334

v != r


Hash: SHA1

Version: BCPG v1.39


data hashed (in hex): 3031323334353637383961626364656604011102001b05024fed084d141c616263203c6d616b636d406161612e636f6d3e04ff00000021

r = 700580719365380086754774917458461236187098909186
s = 103881812262595813943381509986903840453887782603

w = 178510125628083028184051840492924307896586330444 // s^-1 mod q
u1 = 78831508775508876446567239486098677466912246622
u2 = 572875590470993668032596348682349224460207395691
v = g^u1 * y^u2 % p % q = 700580719365380086754774917458461236187098909186

v == r

what data did i not include in the hash / what did i do wrong?


share|improve this question
cross posted and answered on SO:… – CodesInChaos Jul 9 '12 at 21:36
it did take over a week to get an answer. i had hoped to get an answer sooner, by posting in multiple places. anyways, should i delete this, or leave it up? – calccrypto Jul 9 '12 at 21:45
up vote 1 down vote accepted

Quoting the original answer at StackOverflow

Haven't got enough time to look up the details, but I would guess that you're applying (or not applying) padding correctly. That would cause the right result to come up for some input lengths, but not for others.

I guess I'll look into this more, but I wanted to get something in under the bounty wire :)

Edit: Ok, found an error. Not sure why you're getting it, but if it's fixed, then the right answer comes out. In your not-working example, you calculate w (s^-1 mod q) as

 w =  702955297882281869313155599553522395227576660460 // s^-1 mod q

but I get

 w =  702955297882281869313155599553522395227576660458

off by 2! Really, really close values though. And it can be shown that mine is right:

s * your_w mod q = 308227306159276200906356361486529830038073078504

s * my_w mod q = 1

If you plug in this w value, you then get

u1 = 536931432138658080437983667536052790245747416035
  u2 = 591698847955233800072578903940910445457030802333
  v = (g^u1 * y^u2) % p % q = 666804200764671083282351405489424949903645052927
  r == v

Hope that helps.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.