You need a server between (as Manfred mentioned SMS is not usable as you need to read/send SMS in your app which is restricted on actual Android versions) which handles all the messages (probably with a database). B4J is a good choice on servers where you can run own sw (like VPS). PHP can be used on any cheap hosted solution.
Use FCM (Firebase Messaging) for messages up to 4 KB or at least to push an info that there is a message (like WhatsApp and other messengers do). Think about a user registration and security features. Every client needs an own private and public key. The public one needs to be exchanged, stored and maybe updated. Another to do for you app.
Use the search function and you'll find tons of examples (RSA, AES, PHP, B4J-Server, Databases, Firebase, etc.). Please take care that this is a huge project.