simple crypto solution(s)?

List,

I am trying to solve a little problem, but since I don't have much idea 
about cryptography tools on linux, I would like to get some pointers 
from this list. Also, if the problem I have develops to something big, 
there may be a paid consulting opportunity here as well

Two entities (say A and B, non-humans) are connected through a high 
speed, point to point, short distance (say 1m max) serial link. Both 
entities have their own OS and file systems. I need to create a key 
(private/public) pair and send some information (less than 256 bytes) as 
a part of the handshake procedure between A and B (I already have a 
custom protocol to do handshake). Also, I am not bothered about key 
rings or publishing the public keys as the project targets a private 
system, not connected to internet, but _CANNOT_ use symmetric keys.

My questions are:

How do I create a (moderately) strong key pair in linux for asymmetric 
encryption?

What are the tools used?

Do these tools have APIs and source code available (this is most important)

Thanks much,

Lister