A data communication apparatus which is capable of easily selecting a desired encryption scheme that is appropriate to the size of data that is to be transmitted. A key to be used for encryption is acquired. An encryption means corresponding to the acquired key is searched. The period of time required for encryption of data to be transmitted by the searched out encryption scheme is calculated. Encryption means candidates for encrypting data to be transmitted are determined based on the calculated period of time required for encryption. A user is notified of the determined encryption means candidates in a selectable manner together with the period of time required for encryption.