From: nobody@REPLAY.COM (Anonymous)
Date: Sun, 30 Nov 1997 11:48:07 +0800
To: cypherpunks@Algebra.COM
Subject: Digital Signatures
Message-ID: <199711300337.EAA14202@basement.replay.com>
MIME-Version: 1.0
Content-Type: text/plain



You can't see it up here, but this is a signed message using a
protocol which is modestly titled "Cantsin Protocol No. 1".
Suggestions for improvement are most welcome.

At the bottom of this message you will find a series of hexadecimal
numbers expressed in ASCII which comprise the signature.  I considered
using ASCII armor or uuencode to store the information, but the
straight numbers are easier to work with.  That is, the components of
the signature are easily manipulated using off the shelf tools such as
Perl.  Also, because certain numbers are freely accessible, the
message is easy to filter without necessarily calling other programs.
It makes it easy to find signed messages using search engines which
are not necessarily aware of encryption protocol formats.

Having the numbers exposed has a nice feel.  It lets you see exactly
what is going on.  It encourages people to investigate the meaning of
the numbers and to think about the information a signature really
conveys.

Cantsin Protocol No. 1 uses El Gamal to sign hashes generated by SHA1.

Executive summary of the signature format:
<Cantsin Protocol No. 1 code> <comments>
<SHA1 hash of public key components>
<SHA1 hash of message>
<offset> <length>
<a>
<b>

The first line is "16A5942B6EED349ECF4594C784DFD177 [Cantsin Protocol
No. 1]".  The hexadecimal number was chosen randomly and is the
indicator that this is a Cantsin Protocol No. 1 signature.  The number
was chosen randomly and it is somewhat unlikely that anybody else will
accidently choose it.  The text following the number is just there so
a human reading it will know what they are looking at.  No program
should rely on that text.

The signature begins where the code (i.e., "16A59...") begins - it
need not be preceded by a newline.  (It can be used to sign anything,
in other words.)

The public portion of an El Gamal key consists of three variables p,
g, and y.  p is a large prime, g is a randomly chosen number, and y is
computed using the secret key.  (See "Applied Cryptography" for the
details.  I'm using Schneier's nomenclature.)

Monty Cantsin's public authentication key is:
p: E0D087F3BA00B808E24606F13681AEAE702E2FD49F52DBBFB7B6C67606183FE42466FBB953858C3E618BED52E6EB15A0AFD4607AEA3B4D747A4A3A5D3CDDA0FB5DE59115ACCEC4E1F7A95D81814CF0CB0CA5F2342C809F92533CE1EEE96C352D6116A88B353881B594036C317A0EED2AE62FDEE4A7D8BBF077CCD8702268FD16FBDC7100A35BF9C02D187871B2F727D654174A73A72C2E24C9EA1826322779FDE2E21BF6DF99A895C379362FB45DF54CAE1CD3609DFCF3EC60E8C0513C87FF6EA46083CE1074491EDB63F804DCDCACAE3755739951D2FE22C57601DAD1742AE543209D107A32EAFE45976104190C759E1B50763EA3E3526FED3ED4F567DC00B9
g: 5B4A84924FFF2B5282DA28879EFA3017D316F8B76FF153D2A647C53BF557E68A62C6F644719683C4A249EB9892DC3B2EADCFF55D2BFC371482563CA38D628C35BF717EE3A1CF6BCED68BAFF584C5F2F7163D9154707B39A13622E790ABE5723E4725CFC434488DD2E28C682F7C8A3FF99BA6A7E4A9EFAF35599D674FB0326BD1E36460AEE2752CD485CAA29758BFDF46F31D8614A5F820EE7F570AEA7F3E2ECF94CBB4A9482AF64C5ACC9319FCA2E990B978CC4A023AE82CB8972CE66BC45C4EF3E5BF25349096F46B78D265D39C253FDC4498D52D2283660FA5616DB26D6FED62E4C4509D316577A06DE75BFCA196D77573602F72C634D93121F7E61A480024
y: A7006552F14B2F34E80B79BD51558578771327BA2E758109F28C9C455E620ADF475C8513DF4466717961FC82A979110D8389C9CE740EBFAFB57F53B443F311F62B17814BBC2967DE63879B18B7E22E0998EA6615DF599FB956FE4A5F20BEB26E81F7BFE275FAD9F98E139E31E621229FA525246B30F626B90935B37AF2CB22956419CADBD4FB3A9EAF5E3821D8EA10327167BA1A34D04F6EF23F40F2857F071497398E4DDACAA8840F062433AF29A3705F7CAD7CF5F4F59C56EC7228AE011D372C4DE6D6708971400B70401573E9832142DF5CB56726103093F6290F6EF9E9FAD75A4786917ED6F97862F1D7E66CDCB874981B8DB088B101689FF6103D431824

(This key should not be used for communication.  It is not very well
secured.  Also, I like Adam Back's assertion that authentication keys
should be different from communications keys.)

The second line in the signature is an SHA1 hash of the public key.
The hash is computed on the concatenation of the hexadecimal ASCII
forms of p, g, and y respectively.  There should be no leading zeros.
(Remember to leave off the newline!)

The third line is an SHA1 hash of the message itself.

The fourth line contains an offset and a length to specify the area of
the text which is signed.  The offset is relative to the signature
itself.  That is, the first character of the Cantsin Protocol No. 1
code is at position 0.  As signatures are usually appended, the offset
will usually be the additive inverse of the length.

This is an unobtrusive and highly flexible signature format.  No text
is modified to accommodate the protocol.  No information needs to be
prepended to the text.  This means that signing a document only makes
it longer at the end - the area a reader cares the least about.  You
can sign as often as you like and it won't really matter that much.
This protocol could be used to sign The Declaration of Independence.

Not only that, but it is possible to be highly selective in what is
signed.  The user could sign a portion of a message without modifying
or sabotaging other signatures.  It is completely compatible with
other signature formats.  Not only can you sign the subset of text
which another user signed, but signatures can even overlap.

The last two lines are the signatures themselves.  El Gamal signatures
consist of two values which Schneier calls "a" and "b".

Note that the signature does not contain a time stamp!  Users who want
time stamps can add one in the text.

El Gamal is simple enough that the signature on this message can be
checked using standard Unix tools such as dc version 1.1.  Let's say M
is the SHA1 hash of the message.  It is checked by verifying the truth
of this equation: (y^a * a^b) mod p = g^M mod p.

(dc version 1.1 has an | operator which is used to compute equations
of the from a^b mod n like: a b n |.  The left side of the equation
will be easier to compute if you compute ((y^a mod p) * (a^b mod p))
mod p instead.)

You also need to be able to compute SHA1 hashes.  I've been using
something called "sha1file" which, I believe, originated at Adam
Back's web site.

I have some crude tools for making and verifying these signatures, but
they still need work.  At some point they will be released into the
public domain.

Aside from ordinary message signing, there are at least two good uses
for these signatures.

One is for timestamping services.  Since the signature is unobtrusive,
it would be easy to route a message to all known timestamping
services.  The timestamp can only fail if all timestamping services
fail.  Yet, the message would still be completely readable without any
garbage at the top.

Another is for authenticating messages from the distributed
cypherpunks mailing list machines.  Right now it would be somewhat
ugly to have all three machines signing every message.  But, with this
protocol it just makes each message a little longer.  This would
prevent certain kinds of attack and make it harder to exploit a
compromise of any of the mailing list machines.  (It's harder because
an undeniable trail of inconsistency is left even if the compromiser
has the power to sign messages at will.)

Monty Cantsin
Editor in Chief
Smile Magazine
http://www.neoism.org/squares/smile_index.html
http://www.neoism.org/squares/cantsin_10.htm

Subject: Digital Signatures
To: cypherpunks@algebra.com
16A5942B6EED349ECF4594C784DFD177 [Cantsin Protocol No. 1]
AF823675BFB992A1CD9CD2EEBC5CDAE4041E6F06
71EA6E4D747292BC2DBF92422A5AF165470E65EC
-1CB9 1CB9
820BA3DF73E2827DC5AAE14232405404B4E998652F813C0D78126D96C018A6053B8D6E7EC209CEE18D465B971A16DF5806C7D12D2CE0D78E54E7B753420859230935CF0992BBDF5083059053328377C928A12434A553D67A6D203C871C0135F0C7DA8DA0122493ACD7B6C96220CA4001558276FB0F1769C4A8CA1E611900A0ED2913885491DDAECB0FA6EAAD11EC47C4A344BC7ED93B9CE9D21F936B1E29EBCC625FE64CBB2B9AE4FA418761279F6D67ABDC986539A77F48AA3E0C85FFEDFED633F706522A9AEA1B9442361DDD3599ECDCA3D663E50A0F19C7B7C8AAB83C35F237CE51C57808C962FFBEEA2CD2C7D032E9CC0E2AB26BC11AD52FA82298777A33
743AC7C48502DBC6918E339C18CF0AB824F09E635DB302D5DC5D1E3DFF616950A7B9C9E4D27B8502112AE76C7FDE993859E2E3CD589110B81E58BB7DD7AC510564ACB974D800A8C64D387AB62CE83D602E6AE9E8D13A488F56F28CB6D479B6F7F06444828246BBF5C014545D516280181EC3E0B964077A696D6A64454AB93E82357A1F558BE726D9BCA459BB59AD1CD7850ED1BB0AEE6CBB651B7B4F34D73D0AF130949F90F67335045EC4B95A8DAB91700A39A5A331AD8227EC8AE9D60320F1839F6ABD2F871DD8F3579A39920792A7EF4C990E2AAB31CD259800255FDE7D467C39EC6E4FF7DF547E9FE3DF5F57C4C304A01B60B6C453F84C5A56FE0D8AAB77