Can they use quill and parchent?

If so, the usual public key algorithms could be encoded into something like a tax form, i.e. something like "...51. Subtract the number on line 50 from the number on line 49 and write the result in here:__ ...500. The warden should also have calculated the number on line 499. Burn this parchent."

Of course there would have to be lots of error checks. ("If line 60 doesn't match line 50 you screwed up. If so, redo everything from line 50 on.")

To make it practical, each warden/non-prisoner-pair would do a Diffie-Hellman exchange only once. That part would take a day or two. After establishing a shared secret the daily authentication would be done by a hash, which probably could be done in half an hour or less.

Of course most people would have no clue why those forms work, they would just blindly follow the instructions, which for each line would be doable with primary school math.

The wardens would probably spend large parts of their shifts precalculating hashes for prisoners still asleep, so that several prisoners could do their get-out work at the same time. Or maybe they would do the crypto only once a month or so and normally just tell the non-prisoners their passwords for the next day every time they come in.