Generate random in secure message transfer
You can use the well established TLS (Transport Layer Security) protocol to achieve the first three properties and modify it to include a digital signature for non-repudiation*. However, strictly speaking, non-repudiation requires the use of certificates from a CA so that the signature can be verified by any third party.