The devices could exchange their keys through a secure connection - be it direct (Bluetooth, LAN) or routed by a third-party service. It could also be transferred physically (through removable storage, or through retyping a bunch of numbers shown on one device into another device).
