Is this database design correct?
In nutshell that what you are looking for.
You do need composite primary key "binding" those 2 FK in intersection table.
(all attributes are omitted for brevity)

USERS can receive zero - or - more messages
Messages can be sent to one - or - more users.

ps.

Tool i used to generate image is a bit buggy - line bewteen mail_box and Users should be dotted.