Provided is a method of booting an electronic device including a host central processing unit (CPU) and a security module. The method includes: the host CPU starting to boot a system by using boot information in response to a reset or power on event of the electronic device; and when an authentication start instruction is not received by the security module from the host CPU until a first predetermined period elapses after an occurrence of the reset or power on event of the electronic device, controlling an operation of the host CPU by the security module. According to the method, when the authentication start instruction is received before the first predetermined period elapses, the security module authenticates the boot information and controls the operation of the host CPU based on an authentication result. A method of authenticating a boot of the electronic device in the security module is also provided.