I have an Android App that use OTP (One time password) to authenticate the user the first time with their Phone number.
How can I do this in Back-end ? Do I store the phone number ? Do I generate a token ?
As OTP stands for One Time Password, just you need to generate a random number or sth combination of valid characters (token) with a specific length (at least 4 digits) and then store it with creation time for the requesting user in database for evaluation purpose.
This is necessary to store a valid email address before activating OTP mechanism, since a user may lost his phone or change the phone number and there should be a fallback solution in order to set a new one. An email won't change or disturb during the time as it has its own recovery mechanism.
In this way, This is not required to generate a globally unique OTP each time a user requests. The OTP is user specific which is valid for a short time since its generation time. You can implement other security mechanisms like maximum allowed failures or increase the OTP length up to 8 digits (or combining with valid characters, but keep it as short as possible) to enhance it based on your project sensitivity.
This is a deliberate decision to add another recovery/security options like employing Security questions which are very useful in special cases. Now let's answer your questions more detailed:
How can I do this in Back-end ?
You have to store any value (creation time for OTP too) and then do the validation based on them.
Do I store the phone number ?
Yes, You have to store it for each user. You can store some alternative phone numbers too, based on your preferred design. In this way, each phone number should be added in a secure manner, perhaps by validating first(primary) phone number.
Do I generate a token ?
A security token which may be made up of digits or valid characters is required to be generated, saved and sent to the target user, in order to have an OTP validation mechanism.