  This work presents a novel, black-box software-based countermeasure against
physical attacks including power side-channel and fault-injection attacks. The
approach uses the concept of random self-reducibility and self-correctness to
add randomness and redundancy in the execution for protection. Our approach is
at the operation level, is not algorithm-specific, and thus, can be applied for
protecting a wide range of algorithms. The countermeasure is empirically
evaluated against attacks over operations like modular exponentiation, modular
multiplication, polynomial multiplication, and number theoretic transforms. An
end-to-end implementation of this countermeasure is demonstrated for RSA-CRT
signature algorithm and Kyber Key Generation public key cryptosystems. The
countermeasure reduced the power side-channel leakage by two orders of
magnitude, to an acceptably secure level in TVLA analysis. For fault injection,
the countermeasure reduces the number of faults to 95.4% in average.
