Techniques are disclosed for evenly distributing certificate status validity messages across multiple response servers. A certificate authority (CA) may partition subsets of online certificate status protocol (OCSP) responses to each be handled by OCSP response servers. The partitions are based on serial numbers of the underlying digital certificates of the OCSP responses. For example, to determine which OCSP response server is assigned to distribute a particular OCSP response, a modulo operation may be performed between the last octet value of the underlying certificate serial number and the total number of available OCSP response servers of the CA. The result yields a partition number that may be used to identify the corresponding OCSP response server.