What is the best way to prove that you wrote the encrypted message on a piece of paper? As most of us know, many conspirators have died because of false message implants, Mary Queen of Scots, for example.
You have asked about the authentication of a hand-written message, but let's also include an integrity check as a desired service.
Let's say that your message was encrypted with a one-time pad. The following methods of early modern cryptography will not do:
(1) Russian copulation (which is designed to further conceal names, headers, salutations, etc.)
(2) Variable-length padding
(3) Using a reasonably-sized tabula recta
Plaintext (your message): DONOT NEGOT IATE Truly random key: JQOXF RMSUA PWBI ------------------- Ciphertext: MEBLY EQYIT XWUM
Variable padding added:
KIPXQ NECEM EBLYE QYITX WUMRZ NUDOA DIEHL ARAIT EMONG ESEBO SLAVO
But this is no solution. People used to simply take it for granted that the message was authenticated because their pre-shared symmetric key worked to decrypt it.
However, one could take advantage of having pre-shared secrets, especially with the OTP because this must have already been done anyway. First, determine the size limit of the ciphertexts that will be sent. For example--choose thirty-one characters-- and draw a box, say 31 columns wide and 34 rows deep. Write the plaintext across the top in the first row. Yes, this is going to be a short message, but notice that this system might be amenable to using code. Next, under each character of the plaintext, write the predetermined 31-character authenticator for that character. For example:
DONOT NEGOT IATE (__truly random, pre-established, one-time, filler__) DONO... FTID... GWOZ... NRFG... RIUW... QESD... JFLK... GUEE... MUNF... ARAI... TEMO... NGES... EBOS... LAVO... WAZY... QLYX... etc. etc.
To clarify, this means that each character in the plaintext will have a thirty-one character authenticator, and these will always be different (which recalls homophonic substitution and your reference to Mary Queen of Scots).
It is crucial that all of these values be generated in a "truly random" manner.
There will be a table similar to this:
If 1st character is "A" = KFGEIOGZUZDOITSEHAJNWNSYFEBMAXY If 1st character is "B" = BREHYEMKIDHFDDJBDIHTDZGDOODYHWV (etc.) If 2nd character is "A" = VRDABALALAJEOQZFURJVLPQWVMVAECZ (etc.)
So, each character in the ciphertext will correspond to one of the 26 possible authenticators, and this is going to end up being a little booklet of truly random values.
The last two rows will be a truly random authenticator which will match the indicator tag. The indicator tag will appear above the message, and will mainly be used for convenience--to indicate message sequence and which key to use.
For example (which is not to be encrypted):
AVRAL OBESE XIANG POLAR GRIME TIARA HANOI THUGZ
It will, of course, correspond with the shared secret authenticator in the last two rows of the message. Both will be non-sequential. The shared secret authenticator will only be used once. As you can see, the pre-established size of the message is very important.
Again, the authenticator will be 62 characters long and take up the last two rows of the message.
Now, pass your intended one-time pad key over the whole thing.
Note: for this option we could expand the alphabet for added strength. Everything is going to depend on the strength of the key, and a long key it will be.
Using Poly1305 by hand might be a solution, but that is going to take some work. You are also going to have to devise a method for adding that information to your message. Poly1305 has a 32-bit preshared key that cannot be reused. Good advice, coming from forest and, graciously, from Ross J. Anderson himself, says use a Carter-Wegman universal hash function.
Construct a one-time MAC according to these instructions.
I believe you could use Encrypt-last-block CBC-MAC (ECBC-MAC) with random permutations as "block ciphers" and a one-time pad to encrypt the last blocks. See my answer to a similar question. Pretty sure the scheme is secure