Abstract: Based on the random masking scheme，several fine grained masked primitives are defined.Then all the transformations in AES are decomposed to these primitives.And all the intermediate results are masked by different random values.To implement AES based on randomly masked primitives efficiently，three kinds of extended instructions are defined.Combined with random scheduling scheme，the whole execution flow of AES is presented.It is pointed out that this approach can prevent against first order and high order power analysis attack.Experiment results show that it has the advantage of security，performance and hardware complexity in comparison with several other countermeasures.