In today's era, saying someone's work is based on someone else's work is equivalent to calling the former as ungrateful and the latter as unacknowledged. We tend to relate things and find patterns in similar things, but we fail to grasp the real exquisite feeling that produced the work. It happened with every subject at some point in history where people thought that someone's work was inspired or based on someone else's work. A very famous example from mathematics is who invented calculus, as there was an intense debate and heated arguments over who came up with the idea of calculus, was it Leibniz or was it Newton? Later it was found that both of them independently came up with the same concept.
There is no doubt that King's Rita Hayworth and Shawshank Redemption has the very same nature which Tolstoy's God sees the truth, but waits (written 110 years before King's) has. Hope is dignified in King's novella, while in Tolstoy's story hope is given up:
Remember that hope is a good thing, Red, maybe the best of things, and no good thing ever dies.
And Aksyónof wrote no more petitions; gave up all hope, and only prayed to God.
So, there is a kind of intense similarity between them. In both works we find that the main characters (prisoners) get a good reputation among other convicts and become a judge, to quote from God Sees the Truth, but Waits:
and his fellow-prisoners respected him: they called him 'Grandfather,' and 'The Saint.' When they wanted to petition the prison authorities about anything, they always made Aksyónof their spokesman, and when there were quarrels among the prisoners they came to him to put things right, and to judge the matter.
Similarly, in King's novella, Andy trades with Hadley for beer for his fellow prisoners, and even tried to teach Tommy some basics. And the most important of all is that in both of the works, the main character (and us) get to know who actually committed the murder. So, they are very profoundly similar. We can argue that King's novella is based on Tolstoy's story, someone can argue that they are not similar as both of them have a very different endings which matters a lot. An educated man can argue for anything, no matter how absurd or self-evident the topic is.
I cannot find any interview or things like that where Stephen King disavowed or even discussed the matter. Here is a blog which discusses the same issue, but still we don't find Stephen King denying or confirming that his novella is based (loosely or not) on Tolstoy's short story.
