Oldest known instance of a handshake that i could find is in this babylonian tablet. http://oracc.museum.upenn.edu/saao/aebp/images/essentials/countries/babylonia2-large.jpg

Its of two different kings (assyrian and babylonian) king hands in public and was to reflect a time of peace. Similar images can be found in other ancient works of art.

In this piece http://www.theoi.com/Gallery/P14.3.html theseus is being welcomed by posidon and shaking hands. This is of two different cultures and a few thousand years apart. Suggests the idea of the handshake is a sign of goodwill going back to early history.

This might be more of a question for r/AskAnthropology.