Short message service (SMS) and Unstructured Supplementary Services Data (USSD) are a very popular and easy to use communications technology for mobile phone devices. Originally, these services were not designed to transmit secured data, so the security was not an important issue during its design. Yet today, it is widely used to exchange sensitive information between communicating parties i.e. HelloCash, Ethio Gebeta, Lehulu, CBE M-banking, 8100, 8400 and so much more. Due to the vulnerable nature of SMS and USSD this paper proposes an alternative solution that provides a client-server SMS and USSD security protocol that guarantees provision of confidentiality, authentication, integrity, non-repudiation, and file compression security services. A hybrid cryptographic scheme is used which combines the Identity Based Encryption (IBE) and AES-Rijndael algorithms without key distribution servers and certificate authorities to achieve more robust functionality. HMAC-SHA256 hashing algorithm will be used to generate a message digest. IBE will be used to digitally sign the message and to encrypt the encryption key used on AES. LZW compression will be used to compress the SMS. Unlike any previous works that involve certificate authority and key management, this protocol is proposed to be used in mobile banking and payment once a user successfully subscribes to the service.