I am not an expert on this and it's just my understanding from general history things.

I think wax seals were a big part of it. If you have a ring you can make a bunch of wax seals but it's really hard to make a copy of the ring from a wax seal. Give each general a document with the royal seal on it and the next time they get an order with the royal seal you can compare it with the seal you already have. If you use the wax seal to close the letter so that you need to break the wax to open the letter you can be fairly certain that the one with the ring that wrote it and that nobody else has opened it.

I also think chains of commands is important. King gives letter to messenger Steve. Steve then gives it to Dave and Dave knows who Steve is so he trust the message. Dave then gives it to Rodney and Rodney gives it to a Lord. Each person knows who the person they are getting a message from is so the chain is trusted. Should Ivan kill Dave and try to give a fake message to Rodney they Rodney would just go "where the fuck is dave" and not deliver the message.