Privacy is a very important requirement for viability of modern information sharing through cyberspace and the modern cryptology is ensuring success. Harmony Search Algorithm (HSA) is a new meta-heuristic computation technique inspired from musical improvisation techniques, where searching for a perfect harmony is the objective of this technique. Public Key Cryptography heavily relies on key pairs which are large prime numbers. Our adaptation of the HSA tries to provide a fast key generation mechanism with a feasible implementation. The keys are ranked based on their harmony and the best harmony is selected as the result of the search which in turn is used to generate the key pair of RSA, a Public Key Cryptography technique as a test of effectiveness and success. © Springer Nature Singapore Pte Ltd. 2019.