Is DB Normalization done purely based on the primary key or is it done based on all the candidate keys?
Normalization is concerned with all Candidate Keys. A Primary Key is just a candidate key. Primary keys are no different to any other candidate key.

Potential confusion arises because in the early days of relational database theory the term Primary Key used to mean any and all candidate keys whereas modern usage is that Primary Key means only one key that is "preferred" or deemed to have some special significance for database users. Unfortunately many of the "definitions" you will see online or even in print are wrong as a result.