In this paper, we propose a novel directional modulation (DM) scheme based on random frequency diverse arrays with artificial noise (RFDA-DM-AN) to enhance physical layer security of wireless communications. Specifically, we first design the RFDA-DM-AN scheme by randomly allocating frequencies to transmit antennas, thereby achieving two-dimensionally (i.e., angle and range) secure transmissions, and outperforming the state-of-the-art one-dimensional (i.e., angle) phase array (PA) based DM scheme. Then we develop the closed-form expression of a lower bound on the ergodic secrecy capacity (ESC) of our RFDA-DM-AN scheme. Based on the theoretical lower bound derived, we further optimize the transmission power allocation between the useful signal and artificial noise (AN) in order to enhance the ESC. Simulation results show that 1) our RFDA-DM-AN scheme achieves a higher secrecy capacity than that of the PA based DM scheme, 2) the lower bound derived is shown to approach the ESC as the number of transmit antennas N increases and precisely matches the ESC when N is sufficiently large, and 3) the proposed optimum power allocation achieves the highest ESC compared with other power allocations in the RFDA-DM-AN.