Substitution boxes are an important cryptographic primitive. Design techniques based on mathematical transformations, a design technique of these cryptographic primitives, have played a particularly important role in the block encryption algorithm known as the Advanced Encryption Standard (AES). Because AES substitution box structure has the best cryptographic properties. However, various weaknesses arise when the implementation attacks are considered. Although the cryptographic properties of substitution box structures based on random selection techniques are worse than the AES substitution box structure, they are more successful to prevent implementation attacks. The aim of this study is to investigate the performance improvement algorithms of substitution boxes based on random selection. In this study, it has been shown that performance improvements of substitution boxes based on random selection can be achieved with the proposed post-processing algorithms. These results are thought to make significant contributions in the future, especially as a countermeasure for the prevention of implementation attacks.